IP (complexity) - Proof That IP = PSPACE

Proof That IP = PSPACE

In order to prove that IP and PSPACE are equal, we show that IP is a subset of PSPACE and also that PSPACE is a subset of IP, and hence the two are equivalent. In order to demonstrate that, we present a simulation of an interactive proof system by a polynomial space machine. Now, we can define:

and for every and every message history, we inductively define the function :

$N_{M_j} = \begin{cases} 0: j = p\text{ and }m_p = \text{reject}\\ 1: j = p\text{ and }m_p = \text{accept}\\ \max_{m_{j+1}} N_{M_{j+1}}: j < p\text{ and }j\text{ is odd} \\ \text{wt-avg}_{m_{j+1}} N_{M_{j+1}}: j < p\text{ and }j\text{ is even} \\ \end{cases}$

where the term is defined as follows:

where is the probability taken over the random string of length . This expression is the average of, weighted by the probability that the verifier sent message .

Take to be the empty message sequence, here we will show that can be computed in polynomial space, and that . First, to compute, an algorithm can recursively calculate the values for every j and . Since the depth of the recursion is p, only polynomial space is necessary. The second requirement is that we need, the value needed to determine whether w is in A. We use induction to prove this as follows.

We must show that for every and every, and we will do this using induction on j. The base case is to prove for . Then we will use induction to go from p down to 0.

The base case is fairly simple. Since is either accept or reject, if is accept, is defined to be 1 and \Pr = 1 since the message stream indicates acceptance, thus the claim is true. If is reject, the argument is very similar.

For the inductive hypothesis, we assume that for some and any message sequence, and then prove the hypothesis for and any message sequence .

If j is even, is a message from V to P. By the definition of, . Then, by the inductive hypothesis, we can say this is equal to . Finally, by definition, we can see that this is equal to .

If j is odd, is a message from P to V. By definition, . Then, by the inductive hypothesis, this equals . This is equal to since:

because the prover on the right-hand side could send the message to maximize the expression on the left-hand side. And:

Since the same Prover cannot do any better than send that same message. Thus, this holds whether is even or odd and the proof that IP PSPACE is complete.

Here we have constructed a polynomial space machine that uses the best prover for a particular string in language . We use this best prover in place of a prover with random input bits because we are able to try every set of random input bits in polynomial space. Since we have simulated an interactive proof system with a polynomial space machine, we have shown that IP PSPACE, as desired.

Read more about this topic: IP (complexity)

Famous quotes containing the word proof:

“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)