PSPACE ⊆ IP

Inclusion · Sha90

Statement

PSPACE $\subseteq$ IP: the $\mathbf{PSPACE}$-complete language TQBF of true quantified Boolean formulas has an interactive proof — Sha90.

Sketch

Arithmetize the quantified formula over a large finite field and run a sum-check-style protocol, with degree reduction keeping each univariate polynomial the prover sends of low degree.

Notes

• The converse IP ⊆ PSPACE is folklore, so $\mathbf{IP}=\mathbf{PSPACE}$ — Sha90.
• The precursor ${\mathbf{P}}^{\#P}\subseteq \mathbf{IP}$, by arithmetization and the sum-check protocol — LFKN90.