IP is contained in PSPACE

:

Let  be a language in IP. Assume that 's Verifier  exchanges exactly  messages when the input has length  We construct a PSPACE machine that simulates .

First, for any string , we define

This value is at least  if  is in  and is at most  if not. We show how to calculate this value in polynomial space. Let  denote a message history  We generalize the definition of the interaction of  and  to start with an arbitrary message stream . We write  accept if we can extend with messages  through  so that

1. for $0 \leq i
2. for $j \leq i<p$, where="" $i$="" is="" an="" odd="" number,="" $p\left(w,="" m_{1}="" \#="" \cdots="" m_{i}\right)="m_{i+1}$;" and<="" section="">
3. the final message  in the message history is .

Observe that these conditions require that  's messages be consistent with the messages already present in . Define

Here, and for the remainder of this proof, the notation  means that the probability is taken over all strings that are consistent with . If no such  exist, then define the probability to be  We then define

For every  and every message stream  let  be defined inductively for decreasing , starting from the base cases at  For a message stream  that contains  messages, let  if  is consistent with  's messages for some string  and  accept. Otherwise, let  For $j<p$ and="" a="" message="" stream="" $m_{j},$="" define="" $n_{m_{j}}$="" as="" follows.<="" p="">$$N_{M_{j}}=\left\{\begin{array}{ll} \max _{m_{j+1}} N_{M_{j+1}} & \text { odd } j

Let  be the empty message stream. We make two claims about the value  First, we can calculate  in polynomial space. We do so recursively by calculating  for every  and  Calculating  is straightforward. To calculate wt-avg , we go through all strings  of length  and eliminate those that cause the Verifier to produce an output that is inconsistent with  If no strings  remain, then wt-avg  is  If some strings remain, we determine the fraction of the remaining strings  that cause the Verifier to output  Then we weight  by that fraction to compute the average value. The depth of the recursion is  and therefore only polynomial space is needed.

Second,  equals  accepts  the value needed in order to determine whether  is in  We prove this second claim by induction as follows.

CLAIM : For every  and every 

We prove this claim by induction on  where the basis occurs at  and the induction proceeds from  down to 0

Basis: Prove the claim for . We know that  is either  or . If  is ,  is defined to be 1 , and  accepts  starting at  because the message stream already indicates acceptance, so the claim is true. The case when  is reject is similar.

Induction step: Assume that the claim is true for some  and any message stream . Prove that it is true for  and any message stream  If  is even,  is a message from  to . We then have the series of equalities:

Equality 1 is the definition of . Equality 2 is based on the induction hypothesis. Equality 3 follows from the definition of  accepts  starting at . Thus, the claim holds if  is even.

If  is odd,  is a message from  to . We then have the series of equalities:

Equality 1 is the definition of  Equality 2 uses the induction hypothesis. We break equality 3 into two inequalities. We have  because the Prover that maximizes the lower line could send the message  that maximizes the upper line. We have  because that same Prover cannot do any better than send that same message. Sending anything other than a message that maximizes the upper line would lower the resulting value. That proves the claim for odd  .

TQBF is in IP

TQBF is PSPACE-complete

#SAT is in IP