IP = PSPACE

Remarks

The inclusion $\mathrm{IP} \subseteq \mathrm{PSPACE}$ holds because, for a fixed verifier, the largest acceptance probability over all provers can be computed by a recursion over the tree of messages, in polynomial space. For $\mathrm{PSPACE} \subseteq \mathrm{IP}$ it suffices to give a protocol for the PSPACE-complete true quantified Boolean formula problem. The formula is arithmetized: it becomes a polynomial expression over a finite field $\F_p$ for a large prime $p$, with $\exists$ and $\forall$ turned into sums and products over $\set{0,1}$. The prover then strips the quantifiers one at a time, each time sending a univariate polynomial that the verifier checks at a random point, as in the sumcheck protocol. Degree-reduction steps keep these polynomials of small degree, so that a false claim survives a random check only with small probability.

Going deeper

For a student

Adi Shamir proved the theorem in 1990, building on the protocol of Lund, Fortnow, Karloff and Nisan for the counting class $\#\mathrm{P}$ and on arithmetization. The result does not relativize: there are oracles relative to which IP and PSPACE differ, so the proof avoids the relativization barrier. Its methods, arithmetization and low-degree testing, led to the PCP theorem.