IP ⊆ PSPACE

Inclusion · folklore

Statement

IP $\subseteq$ PSPACE: for every $\mathbf{IP}$ verifier, the maximum acceptance probability on input $x$ over all prover strategies is computable in space polynomial in $|x|$ — folklore.

Sketch

Fix the verifier, which tosses $r=\mathrm{poly}(|x|)$ coins. For a partial transcript $\tau$, let $N(\tau )$ be the maximum, over prover continuations, of the number of coin strings in $\{0,1{\}}^r$ consistent with $\tau$ on which the verifier accepts; then $N(\tau )={\max }_{m}N(\tau m)$ over the prover’s next message $m$ at prover moves, and $N(\tau )={\sum }_{a}N(\tau a)$ over the verifier’s next message $a$ at verifier moves. Depth-first evaluation over the polynomial-depth interaction tree uses polynomial space, and $x$ is accepted iff the maximum acceptance probability $N(\epsilon )/2^r$, for the empty transcript $\epsilon$, is at least $2/3$.

Notes

• The converse PSPACE ⊆ IP holds, so $\mathbf{IP}=\mathbf{PSPACE}$ — Sha90.
• For almost all oracles $A$, ${\mathbf{IP}}^A\ne {\mathbf{PSPACE}}^A$ — CCG+94; see the refutation of the random oracle hypothesis.