Symptom

You have a claim you cannot check. A cloud provider ran a computation on a petabyte you do not have and reports an answer. A model was trained on data you cannot access. A database returned an aggregate over rows you are not permitted to read.

The obvious options are both bad: trust the answer, or redo the work. If redoing it were feasible you would not have outsourced it.

The framing that seems to settle it is NP. A claim is checkable if it has a short certificate, so if your claim has no short certificate, you cannot verify it. And many claims plainly have none. “This formula is unsatisfiable” — the certificate would have to rule out all $2^n$ assignments. “White has no forced win from this position.” “This database contains no record matching the query.” These are co-NP-ish statements with nothing short to show.

Passive checking of a static proof is not the only option. If you are allowed to ask questions, and to flip coins the prover cannot predict, the class of things you can verify grows to a size nobody expected.

Statement

An interactive proof system is a conversation between a computationally unbounded prover $P$ and a probabilistic polynomial-time verifier $V$.

Completeness. If the claim is true, $V$ accepts with probability $\ge 2/3$. Soundness. If false, no prover, however powerful or dishonest, makes $V$ accept with probability $> 1/3$.

$\mathbf{IP} = \mathbf{PSPACE}$.

$\mathbf{IP}$ is the class of languages with an interactive proof system using polynomially many rounds and a polynomial-time randomized verifier. $\mathbf{ PSPACE}$ is the class decidable in polynomial space. LFKN (Lund, Fortnow, Karloff, Nisan) established $\mathbf{coNP} \subseteq \mathbf{IP}$ via the sum-check protocol; Shamir extended it to all of $\mathbf{PSPACE}$; the containment $\mathbf{IP} \subseteq \mathbf{PSPACE}$ is the easier direction, by computing the optimal prover’s acceptance probability with a polynomial-space recursion over the game tree.

The size of this is easy to understand and easy to under-feel. PSPACE contains NP, co-NP, the entire polynomial hierarchy, generalized chess and Go, and QBF. A polynomial-time verifier with coins and questions can be convinced of any of it, by an untrusted party, to arbitrary confidence.

Argument

Why the shock. Before 1990 the consensus pointed the other way. Fortnow and Sipser showed there is an oracle relative to which co-NP $\not\subseteq$ IP, which by the standards of the time was strong evidence that interaction did not help much. Then the theorem was proved with a technique that does not relativize (T030), which is why the barrier results and this result belong adjacent: this is the concrete demonstration that a non-relativizing technique exists and works.

The whole trick is arithmetization. A boolean formula is rigid; you can only plug in 0 and 1, so checking all assignments means checking all $2^n$. Replace each connective by arithmetic over a large finite field $\mathbb{F}_p$:

$$x \wedge y \mapsto xy, \qquad \neg x \mapsto 1 - x, \qquad x \vee y \mapsto x + y - xy$$

The result is a low-degree polynomial agreeing with the formula on ${0,1}^n$ — and now defined everywhere else too. That is the entire idea. A liar must now lie about a polynomial rather than about a bit vector, and polynomials are rigid in a way bit vectors are not: two distinct polynomials of degree $d$ over $\mathbb{F}_p$ agree on at most $d$ points, so a random point catches a lie with probability at least $1 - d/p$.

The sum-check protocol, which is what actually runs. To verify $\sum_{x_1,\dots,x_n \in {0,1}} g(x_1,\dots,x_n) = K$:

  1. $P$ sends the univariate polynomial $g_1(X) = \sum_{x_2,\dots,x_n} g(X, x_2, \dots, x_n)$, as coefficients.
  2. $V$ checks $g_1(0) + g_1(1) = K$, and that the degree is small enough. If not, reject.
  3. $V$ picks a random $r_1 \in \mathbb{F}_p$ and sends it.
  4. Recurse on the claim $\sum_{x_2,\dots,x_n} g(r_1, x_2, \dots, x_n) = g_1(r_1)$, with one fewer variable.
  5. After $n$ rounds, only $g(r_1,\dots,r_n)$ remains, and $V$ evaluates it directly.

The verifier never sums over $2^n$ points. It does $n$ rounds of $O(d)$ work and one final evaluation.

Why a liar is caught. If the original sum is wrong, then $P$’s $g_1$ must differ from the true $g_1$, or step 2 fails immediately. Two distinct polynomials of degree $\le d$ agree on at most $d$ of the $p$ field elements, so a random $r_1$ lands on an agreement point with probability at most $d/p$. Otherwise the claim passed down to round 2 is also false, and the argument repeats. Union bound over $n$ rounds: total cheating probability at most $nd/p$.

Numbers make this concrete. For a formula with $n = 100$ variables and degree bound $d = 100$ per round, with a 128-bit prime $p \approx 3.4 \times 10^{38}$, the soundness error is at most $nd/p \approx 10^4 / 3.4\times10^{38} \approx 2.9 \times 10^{-35}$. The verifier has checked a statement about $2^{100} \approx 1.3 \times 10^{30}$ assignments, using 100 rounds of arithmetic, with a failure probability far below that of the hardware being struck by a cosmic ray mid-computation.

Shamir’s extension. QBF adds quantifier alternation, so arithmetization gives $\forall x \mapsto \prod$, $\exists x \mapsto$ a sum-like operator. The danger is degree: each product can double the degree, and $n$ alternations give degree $2^n$, which destroys the soundness bound. Shamir’s fix is a degree reduction operator applied between rounds, using the fact that on ${0,1}$ we have $x^k = x$, so multilinearizing after each step keeps the degree bounded while preserving the value on the boolean cube. That is the technical heart, and it is bookkeeping in service of the same one idea.

Forbids

Ruling out interactive verification of a PSPACE-hard problem. Any claim “this cannot be verified efficiently because it has no short certificate” is about NP and does not survive the addition of interaction and randomness.

Believing relativization settles interactive complexity. The Fortnow–Sipser oracle exists and the theorem is true anyway, which is the cleanest available demonstration that oracle results are evidence about techniques rather than about truth.

A deterministic verifier achieving the same power. With no coins, the prover predicts every question and precomputes a transcript, collapsing IP to NP. Randomness is not an optimization here; it is the entire mechanism.

Soundness against a computationally bounded prover being the same theorem. IP’s soundness holds against unbounded provers. Weakening to bounded provers gives argument systems, which are different objects with different, often better, efficiency.

Does not forbid

It does not mean the prover is efficient. This is the misreading that makes people think verifiable computing was solved in 1990. The honest prover in sum-check does exponential work in general. What the theorem gives is a cheap verifier, and the entire subsequent field is about making provers practical for restricted classes of statement.

It does not mean this is impractical. The line from here to deployed systems is direct. GKR (2008) made the prover efficient for bounded-depth circuits; zk-SNARKs and zk-STARKs descend from arithmetization; Groth16, PLONK, and STARKs run in production. Ethereum’s zk-rollups verify millions of transactions with a proof checked in milliseconds, and the sum-check protocol itself is live inside modern systems: Lasso and Jolt are built directly on it. This is a 1990 theorem with a current production deployment.

It does not require zero knowledge. IP says nothing about hiding. The sum-check prover reveals a great deal. Zero-knowledge (T077) is an additional property obtained by additional construction.

It does not need many rounds in every case. Graph non-isomorphism, the classic example of a statement with no obvious certificate, has a two-message proof: the verifier privately picks one of the two graphs, permutes it randomly, and asks which it was. An honest prover can tell; if the graphs are isomorphic, no prover can do better than guessing.

It does not say $\mathbf{P} \ne \mathbf{PSPACE}$. If they were equal the theorem would be trivially true and useless. It is a statement about verification, and it is conditional on nothing.

Boundary

  • Polynomially many rounds. Constant-round interactive proofs are much weaker; AM and MA sit low in the hierarchy, and collapsing them would collapse PH.
  • Private randomness is not needed. Goldwasser–Sipser showed public-coin proofs are as powerful up to two rounds, so $\mathbf{IP} = \mathbf{AM}[\text{poly}]$. The verifier need not hide its coins, only generate them after the prover has committed.
  • Multi-prover changes the class. $\mathbf{MIP} = \mathbf{NEXP}$ with two non-communicating provers, and the quantum version $\mathbf{MIP}^* = \mathbf{RE}$ (2020) is a genuinely astonishing extension: two entangled provers can convince a polynomial-time verifier of any recursively enumerable statement, including the halting of a given machine.
  • Soundness is statistical, never absolute. The verifier can be fooled with probability $2^{-k}$, and $k$ is yours to choose.
  • The prover must be able to compute. For a PSPACE-complete statement, the honest prover needs PSPACE. The theorem is about what can be checked, not about what can be produced.

The reframe worth keeping: a proof does not have to be a document you read. It can be a conversation you have, and the second kind can establish things the first kind cannot.