Back to Computational Complexity
Back to notes

# Multi-prover IP, probabilistic OTM, and 2-prover IP

95%

In this note, we are going to prove the equivalence between multi-prover interactive proof system and probabilistic oracle Turing machine (probabilistic OTM).

## Multi-prover IP = Probabilistic OTM

In the early 90s, Fortnow, Rompel, and Sipser showed the equivalence of multi-prover interactive proof and probabilistic oracle Turing machines.

A language $L$ is accepted by a probabilistic oracle TM iff $L$ is accepted by a multi-prover interactive proof systems.

• (multi-prover => probabilistic OTM)

Construct an oracle that can verify the conversation between the prover and the verifier.

• (probabilistic OTM => multi-prover)

Use the first prover to give oracle answers and use the second prover to check if the answers are correct. As the two provers cannot communicate and the queries are random, the probability that cheating prover is not caught is at most $(1-n^{-c})$ by the definition of probabilistic OTM. Thus, after polynomially many consistency checks, the error can be reduced to exponentially small.

### Oracle versus Prover

Before we go into the proof, let’s first think about the difference of oracles and provers.

What’s the main difference between oracle and prover? The answer is the power of adaptiveness. That is, the prover can records the previous communication transcript and responds while the oracle is stateless.

However, both prover and oracle are modeled as deterministic function mathematically. Thus, sometimes it confuses people at first glance. To introduce their difference, in the definition of interactive proof, the verifier will feed the previous communication history to the prover as inputs while in OTM, the Turing machine does not necessary to include the previous information as an input to the oracle.

### Proof of the equivalence of multi-prover IP and probabilistic OTM

• (multi-prover => probabilistic OTM)

This is the simpler direction. Clearly that one can use an oracle to simulate multi-prover interactive proof as one can index each provers and encode the indices of the provers as a part of the input to the oracle. Afterward, use Turing machine with randomness to simulate the verifier.

• (probabilistic OTM => multi-prover)

The first idea is to use a single prover to simulate the oracle in the probabilistic OTM and use the verifier to simulate the probabilistic TM. However, one can immediately see that we cannot guarantee the soundness since the prover knows the history of the communication so that we don’t know how to transform the prover into an oracle. That is, we want to find a way to extract an oracle out from the prover(s) so that the soundness of multi-prover IP can be guaranteed by the soundness of the probabilistic OTM. (See the next subsection for details.)

As a result, we introduce more provers, which are independent to each other, as a consistency check so that we can make sure that the consensus of these provers are not so far away from a fixed oracle in the beginning of the protocol.

Concretely, consider $x\notin L$ and let $M$ be the probabilistic OTM that solves $L$. By definition, for any oracle $O$, $M^O(x)=1$ with probability at most $n^{-c}$ for some $c$. Now, our goal is to design a multi-prover protocol such that

• it has perfect completeness and
• when $x\notin L$, if the protocol accepts with constant probability, then there exists an oracle $O’$ such that $M^{O’}(x)=1$ with probability > $2^{-n}$.

Let’s define the multi-prover protocol we are going to use as follows.

### Use multi-prover IP to simulate probabilistic OTM

1. Suppose $M$ runs in $n^k$ steps. Then define a protocol with verifier $V$ simulating $M$ and $4n^{k+1}$ provers $P_1,\dots,P_{4n^{k+1}}$.
2. Pick oracle $O’$ by taking the majority of the responses from every provers. Note that as long as the provers are deterministic, this can be done in the very beginning of the protocol, i.e., before the randomness.
3. $V$ randomly permute the provers and get $\hat{P}_1,\dots,\hat{P}_{4n^{k+1}}$.
4. $V$ simulates $M$ on input $x$, when $M$ queries the oracle, $V$ sends the same queries to the $n$ provers. Concretely, for the $i$th query, $V$ sends the input to $\hat{P}_{(i-1)n+1},\dots,\hat{P}_{in}$.
• If the provers respond with different answers, then $V$ rejects.
• Otherwise, $V$ feeds the response to $M$ and moves on.
5. In the end, $V$ accepts iff the simulation of $M$ accepts. Otherwise, $V$ rejects.

### Analysis of the above protocol

• (perfect completeness)

Clearly that when all the provers respond the queries exactly the same as the good oracle $O$ of $M$, then $V$ will accepts with the same probability as $M$.

• (soundness)

As $O’$ is fixed before the protocol, clearly that $M^{O’}(x)=1$ with probability less that $n^{-c}$. Now, suppose $V$ accepts, there are two possibilities: