47.03.04 · theoretical-cs / 03-advanced-complexity

Interactive Proofs: IP = PSPACE

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §8.1-8.4 (full proof of IP = PSPACE via arithmetisation and the sum-check protocol, the LFKN protocol for #P, Shamir's extension to TQBF, and the consequences for the polynomial hierarchy); Babai 1985 trading group theory for probability

Intuition Beginner

A proof in mathematics is a static object: a sequence of logical steps written on paper. But imagine a different kind of proof, where you (the verifier) ask questions and receive answers from someone who knows the proof (the prover). The prover is potentially infinitely powerful, but also potentially dishonest. Your job is to catch a cheating prover with high probability, using only your limited computational power.

This is the interactive proof model. The verifier is a probabilistic polynomial-time algorithm. The prover has unlimited computational power. They take turns sending messages. At the end, the verifier accepts or rejects. Two properties must hold: if the statement is true, an honest prover can convince the verifier to accept (completeness); if the statement is false, no prover — no matter how clever — can convince the verifier to accept with more than small probability (soundness).

The class IP collects all languages that have such interactive proofs. At first glance, IP seems only slightly more powerful than NP. After all, NP corresponds to one-round interaction: the prover sends a certificate, the verifier checks it. Adding more rounds and randomness seems like a modest extension.

The shocking result is that IP equals PSPACE. Every problem solvable with polynomial space has an interactive proof, and conversely, every problem with an interactive proof can be solved with polynomial space. This means interaction and randomness together are exactly as powerful as polynomial memory — far beyond NP.

Visual Beginner

The interaction between verifier and prover over multiple rounds.

Verifier V                    Prover P
    |                            |
    |--- random challenge r1 -->|
    |<--- response a1 ----------|
    |--- random challenge r2 -->|
    |<--- response a2 ----------|
    |          ...               |
    |--- accept or reject       |

The verifier sends random challenges. The prover responds. After polynomially many rounds, the verifier decides. A dishonest prover cannot fool the verifier with probability more than 1/3, regardless of its strategy.

property	NP proof	IP proof
Rounds	1 (certificate)	polynomially many
Verifier randomness	none	yes
Prover power	unbounded	unbounded
Soundness	perfect (0 error)	probabilistic ( $\leq 1/3$ )

Worked example Beginner

Consider the problem of deciding whether two graphs $G_{1}$ and $G_{2}$ on $n$ vertices are isomorphic (GI). This problem is in NP but not known to be NP-complete.

An interactive proof for graph non-isomorphism (the complement): the verifier randomly picks one of the two graphs, randomly permutes its vertices to get a graph $H$ , and sends $H$ to the prover. The prover must identify which of $G_{1}, G_{2}$ was the source.

If the graphs are non-isomorphic, the prover (being all-powerful) can determine which graph $H$ came from, and answers correctly every time. If the graphs are isomorphic, then $H$ could have come from either graph with equal probability, so the prover guesses correctly with probability only $1/2$ . Repeating the protocol $k$ times reduces the cheating probability to $1/ 2^{k}$ .

This shows that graph non-isomorphism is in IP, even though it is not known to be in NP. The interaction plus randomness gives the verifier more power than any static proof could.

Check your understanding Beginner

Formal definition Intermediate+

An interactive proof system for a language $L$ consists of a probabilistic polynomial-time Turing machine $V$ (the verifier) and a function $P$ (the prover) such that for every input $x$ :

Completeness: If $x \in L$ , then $Pr_{r} [V^{r} \leftrightarrow P accepts x] \geq 2/3$ , where the probability is over the verifier's random coins $r$ .
Soundness: If $x \in / L$ , then for every prover $P^{*}$ , $Pr_{r} [V^{r} \leftrightarrow P^{*} accepts x] \leq 1/3$ .

The class $IP$ is the set of all languages with interactive proof systems. The constants $2/3$ and $1/3$ can be replaced by any constants with a gap, since amplification by repetition closes the gap.

The sum-check protocol is the key technical tool. Given a multivariate polynomial $g (x_{1}, \dots, x_{n})$ over a finite field $F$ , the protocol allows a verifier to compute $\sum_{x_{1} \in {0, 1}} \dots \sum_{x_{n} \in {0, 1}} g (x_{1}, \dots, x_{n})$ with the help of a prover. The prover sends a claimed value. The verifier checks by induction: the prover claims $h_{1} (x_{1}) = \sum_{x_{2}, \dots, x_{n}} g (x_{1}, x_{2}, \dots, x_{n})$ as a univariate polynomial, the verifier checks $h_{1} (0) + h_{1} (1)$ equals the claimed total and then evaluates $h_{1}$ at a random point $r_{1}$ , recursing on $\sum_{x_{2}, \dots, x_{n}} g (r_{1}, x_{2}, \dots, x_{n})$ ^{[Arora-Barak §8.2]}.

Arithmetisation converts a Boolean formula into a multivariate polynomial over a finite field. For a Boolean variable $x$ , the polynomial $x$ (as a field element) agrees with the Boolean value on ${0, 1}$ . For $\neg x$ , use $1 - x$ . For $x \land y$ , use $x \cdot y$ . For $x \lor y$ , use $1 - (1 - x) (1 - y)$ . The resulting polynomial has degree equal to the formula size and agrees with the Boolean formula on Boolean inputs. Quantifiers become sums and products: $\exists x_{i}$ corresponds to summation over $x_{i} \in {0, 1}$ , and $\forall x_{i}$ to multiplication.

Counterexamples to common slips Intermediate+

"IP is just NP with randomness." IP extends NP in two ways: interaction (multiple rounds) and randomness. Both are essential. A single round with randomness gives the class MA (Merlin-Arthur), which is contained in AM and may be strictly weaker than IP. Multiple rounds of interaction are necessary for the full power of PSPACE.
"The prover in IP is honest." The prover in the completeness condition is honest, but the soundness condition must hold against every possible prover. The protocol must be sound even against a malicious prover that adaptively responds to the verifier's queries.
"Arithmetisation works over the integers." It works over any sufficiently large finite field. The Schwartz-Zippel lemma guarantees that if two distinct polynomials of degree $d$ are evaluated at a random point, they agree with probability at most $d /∣ F ∣$ . Using a large enough field makes the error probability negligible.

Key theorem with proof Intermediate+

Theorem (Shamir, 1990: IP = PSPACE). $IP = PSPACE$ .

Proof sketch. $IP \subseteq PSPACE$ : a PSPACE machine can simulate the interaction by enumerating all possible prover strategies. For each prover strategy, simulate the verifier's random choices and compute the acceptance probability. The optimal prover strategy (maximising acceptance probability) can be found in polynomial space by dynamic programming over the interaction tree. The acceptance probability under the optimal prover determines whether $x \in L$ .

$PSPACE \subseteq IP$ : given a TQBF instance $Q_{1} x_{1} \dots Q_{m} x_{m} \cdot ψ (x_{1}, \dots, x_{m})$ , arithmetise $ψ$ into a polynomial $p_{ψ}$ over a finite field $F$ of size $> 2^{m}$ . Replace each quantifier by the corresponding algebraic operation:

\exists x_{i} \mapsto x_{i} \in {0, 1} \sum, \forall x_{i} \mapsto x_{i} \in {0, 1} \prod .

The result is a quantity $A$ that equals the number of satisfying assignments (for existential) or the product of sub-counts (for universal), adjusted so that $A \neq = 0$ iff the QBF is true. The prover claims a value for $A$ . The verifier uses the sum-check protocol layer by layer: at each quantifier, the prover provides a polynomial claimed to equal the partial evaluation, the verifier checks consistency with the previous round by evaluating at a random point, and the process recurses. After processing all quantifiers, the verifier evaluates the remaining polynomial at a random point and checks against the prover's claim. Soundness follows from the Schwartz-Zippel lemma: at each round, if the prover's claimed polynomial is wrong, the random evaluation catches it with probability $\geq 1 - d /∣ F ∣$ , where $d$ is the degree. Union-bounding over $m$ rounds gives total soundness error $m \cdot d /∣ F ∣$ , which is small for large $F$ . $□$

Bridge. This theorem is the foundational reason randomness and interaction together are as powerful as polynomial space: the arithmetisation of Boolean formulas turns logical quantifiers into algebraic operations that can be verified incrementally through the sum-check protocol, and this is exactly the technique that makes PSPACE accessible to a polynomial-time verifier. The sum-check protocol builds toward the PCP theorem 47.03.05 where a similar arithmetisation is encoded into a static proof that can be checked at a few locations, and it appears again in the design of efficient zero-knowledge proofs 47.06.03 where the prover's responses are designed to reveal nothing beyond correctness. The central insight is that a polynomial of degree $d$ is determined by its values at $d + 1$ points, so a random evaluation is a "fingerprint" that distinguishes distinct polynomials, and putting these together, the entire tower of alternating quantifiers in a QBF formula collapses to a sequence of polynomial identity tests. The bridge is that the TQBF characterisation of PSPACE from 47.02.05 and the algebraic identity testing from the Schwartz-Zippel lemma combine to give the IP = PSPACE equality, which generalises the earlier result that $NP \subseteq IP$ to the full power of polynomial space.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Describe the sum-check protocol for computing $\sum_{x_{1} \in {0, 1}} \sum_{x_{2} \in {0, 1}} g (x_{1}, x_{2})$ where $g (x_{1}, x_{2}) = x_{1} x_{2} + x_{1}$ over $F_{5}$ . Verify that the protocol works correctly for an honest prover.

Hint

The true value is $g (0, 0) + g (0, 1) + g (1, 0) + g (1, 1) = 0 + 0 + 1 + 2 = 3$ .

Answer

True value: $g (0, 0) + g (0, 1) + g (1, 0) + g (1, 1) = 0 + 0 + 1 + 2 = 3 (mod 5)$ .

Round 1: the prover claims $h_{1} (x_{1}) = \sum_{x_{2}} g (x_{1}, x_{2})$ . For $x_{1} = 0$ : $g (0, 0) + g (0, 1) = 0$ . For $x_{1} = 1$ : $g (1, 0) + g (1, 1) = 1 + 2 = 3$ . So $h_{1} (x_{1}) = 3 x_{1}$ . The verifier checks $h_{1} (0) + h_{1} (1) = 0 + 3 = 3$ (matches claimed total). The verifier picks random $r_{1}$ , say $r_{1} = 2$ , and needs to verify $\sum_{x_{2}} g (2, x_{2}) = h_{1} (2) = 3 \cdot 2 = 6 \equiv 1 (mod 5)$ .

Round 2: the prover claims $h_{2} (x_{2}) = g (2, x_{2}) = 2 x_{2} + 2$ . The verifier checks $h_{2} (0) + h_{2} (1) = 2 + 4 = 6 \equiv 1 (mod 5)$ (matches). The verifier picks random $r_{2}$ , say $r_{2} = 3$ , and evaluates $g (2, 3) = 6 + 2 = 8 \equiv 3 (mod 5)$ . Checks $h_{2} (3) = 2 \cdot 3 + 2 = 8 \equiv 3$ . Match, so the verifier accepts. Rubric: full credit for the two-round protocol execution and the consistency checks.

Exercise 6 (hard, symbolic).

Prove that $IP \subseteq PSPACE$ by showing that a polynomial-space machine can compute the optimal prover strategy and the resulting acceptance probability.

Hint

Work backwards from the last message. At each step, the optimal prover maximises the acceptance probability, and the verifier's random choice averages over this optimum.

Answer

Consider the interaction tree of $V \leftrightarrow P$ on input $x$ . Each node is a configuration (message history). Nodes alternate between prover moves (the prover chooses the message) and verifier moves (the verifier's random coins determine the next message). Define $val (v)$ as the maximum acceptance probability achievable from node $v$ with the optimal prover strategy. For a leaf (verifier's decision): $val (v) = 1$ if accept, 0 if reject. For a prover node: $val (v) = max_{m} val (v \cdot m)$ over all possible messages $m$ . For a verifier node: $val (v) = \sum_{r} Pr [r] \cdot val (v \cdot r)$ , averaging over random coins.

The tree has depth $O (p (n))$ for polynomial $p$ . Computing $val$ at the root requires evaluating this recursion. At each node, the PSPACE machine stores the current node (polynomial space), enumerates children, and recurses. The recursion depth is $O (p (n))$ , and each level uses polynomial space. Total: polynomial space. Then $x \in L$ iff $val (root) \geq 2/3$ . Rubric: full credit for the game-tree evaluation and the space analysis.

Exercise 7 (hard, symbolic).

State and prove the Schwartz-Zippel lemma: if $p (x_{1}, \dots, x_{n})$ is a nonzero polynomial of total degree $d$ over a finite field $F$ , then $Pr_{r_{1}, \dots, r_{n} \in F} [p (r_{1}, \dots, r_{n}) = 0] \leq d /∣ F ∣$ .

Hint

Induction on $n$ . Pick a variable $x_{i}$ that appears with nonzero coefficient, factor out its terms, and apply the inductive hypothesis to the remaining polynomial.

Answer

Proof by induction on $n$ . Base case $n = 1$ : a univariate polynomial of degree $d$ has at most $d$ roots by the fundamental theorem of algebra over fields, so $Pr [p (r) = 0] \leq d /∣ F ∣$ .

Inductive step: write $p (x_{1}, \dots, x_{n}) = \sum_{j = 0}^{d^{'}} x_{1}^{j} \cdot q_{j} (x_{2}, \dots, x_{n})$ where $d^{'} \leq d$ is the degree of $x_{1}$ in $p$ and $q_{d^{'}} \neq = 0$ (since $p \neq = 0$ ). Fix $r_{2}, \dots, r_{n} \in F$ uniformly at random. With probability $\geq 1 - (d - d^{'}) /∣ F ∣$ (by induction on $q_{d^{'}}$ ), $q_{d^{'}} (r_{2}, \dots, r_{n}) \neq = 0$ , making $p (x_{1}, r_{2}, \dots, r_{n})$ a nonzero univariate polynomial in $x_{1}$ of degree $d^{'}$ . Conditioned on this, $Pr [p (r_{1}, r_{2}, \dots, r_{n}) = 0] \leq d^{'} /∣ F ∣$ . Total: $Pr [p (r) = 0] \leq (d - d^{'}) /∣ F ∣ + d^{'} /∣ F ∣ = d /∣ F ∣$ . Rubric: full credit for the inductive structure and the degree accounting.

Exercise 8 (hard, symbolic).

Show that graph non-isomorphism (GNI) is in IP by describing a two-round interactive proof and proving completeness and soundness.

Hint

The verifier randomly permutes one of the two graphs and asks the prover to identify which one it came from.

Answer

Protocol: on input $(G_{1}, G_{2})$ , the verifier picks $i \in {1, 2}$ uniformly at random, picks a random permutation $π \in S_{n}$ , computes $H = π (G_{i})$ , and sends $H$ to the prover. The prover responds with $j \in {1, 2}$ . The verifier accepts iff $j = i$ .

Completeness: if $G_{1} \neq ≅ G_{2}$ , the prover (being all-powerful) determines whether $H ≅ G_{1}$ or $H ≅ G_{2}$ . Since the graphs are non-isomorphic, exactly one holds, and the prover identifies $i$ correctly. Acceptance probability: 1.

Soundness: if $G_{1} ≅ G_{2}$ , then $H$ is isomorphic to both $G_{1}$ and $G_{2}$ . The distribution of $H$ is identical regardless of $i$ . Any prover strategy guesses $j = i$ with probability exactly $1/2$ . Repeating $k$ times reduces this to $2^{- k}$ .

Hence GNI is in IP. Rubric: full credit for the protocol description, completeness (probability 1), and soundness ( $\leq 1/2$ per round).

Advanced results Master

The IP = PSPACE theorem has rich technical content and far-reaching consequences. The results below develop the proof machinery and explore the extensions.

Theorem 1 (the sum-check protocol, detailed). Given oracle access to a multivariate polynomial $g$ over $F_{q}$ of degree $d$ in each variable, the sum-check protocol computes $S = \sum_{x_{1}} \dots \sum_{x_{n}} g (x_{1}, \dots, x_{n})$ (sums over ${0, 1}$ ) with $n$ rounds. At round $i$ , the prover sends a univariate polynomial $h_{i} (x_{i})$ claimed to equal $\sum_{x_{i + 1}} \dots \sum_{x_{n}} g (r_{1}, \dots, r_{i - 1}, x_{i}, x_{i + 1}, \dots, x_{n})$ . The verifier checks $h_{i} (0) + h_{i} (1) = h_{i - 1} (r_{i - 1})$ (consistency with the previous round's evaluation), picks a random $r_{i}$ , and continues. After round $n$ , the verifier evaluates $g (r_{1}, \dots, r_{n})$ directly and checks against the final polynomial claim. Soundness error per round is $d / q$ , total $n d / q$ by union bound ^{[Arora-Barak §8.2]}.

Theorem 2 (LFKN: #P is in IP). Lund, Fortnow, Karloff, and Nisan (1990) showed that $# P$ functions can be verified by interactive proofs. Given a Boolean formula $ϕ$ and a claimed count $c$ , the prover arithmetises $ϕ$ to a polynomial $p_{ϕ}$ and the verifier uses sum-check to compute $\sum_{x_{1}} \dots \sum_{x_{n}} p_{ϕ} (x_{1}, \dots, x_{n}) = c$ . This was the key step toward IP = PSPACE, showing that counting (and hence $# P$ ) is within the power of interactive proofs ^{[Arora-Barak §8.3]}.

Theorem 3 (Shamir's extension to TQBF). Shamir observed that the LFKN technique extends from counting to alternating quantifiers. A QBF formula $Q_{1} x_{1} \dots Q_{m} x_{m} \cdot ψ$ is arithmetised by replacing $\exists$ with summation and $\forall$ with the operator $f \mapsto f (0) \cdot f (1)$ (the product over Boolean values, which is 1 iff both $f (0)$ and $f (1)$ are nonzero). The result is a quantity that is nonzero iff the QBF is true. The sum-check protocol at each level verifies the algebraic claim, and the entire computation is checked with $m$ rounds of interaction. The prover needs to work over a field of size exponential in $m$ to ensure low error probability, but the verifier's computation is polynomial time since it only evaluates at random points ^{[Arora-Barak §8.3]}.

Theorem 4 (round reduction). The number of rounds in an interactive proof can be reduced. Goldwasser and Sipser (1986) showed that $IP [k] \subseteq AM [k + 2]$ (Arthur-Merlin with $k + 2$ rounds), and the IP = PSPACE result implies that polynomially many rounds suffice for PSPACE. The relationship between round complexity and computational power continues to be an active area of research.

Theorem 5 (IP and the polynomial hierarchy). Since $PH \subseteq PSPACE = IP$ , every language in the polynomial hierarchy has an interactive proof. This is a consequence of Toda's theorem 47.02.07 and the IP = PSPACE result. The interactive proof perspective gives a uniform treatment of all levels of PH, each requiring a bounded number of interaction rounds.

Synthesis. The foundational reason IP equals PSPACE is that arithmetisation converts the quantifier-alternation structure of TQBF into a sequence of algebraic operations (sums and products) that the sum-check protocol verifies incrementally with each round of interaction, and this is exactly the mechanism that lets a polynomial-time verifier check a PSPACE-computation using randomness and dialogue. The Schwartz-Zippel lemma builds toward the PCP theorem 47.03.05 where polynomial identity testing becomes the basis for locally checkable proofs, and it appears again in zero-knowledge proofs 47.06.03 where the same algebraic structure is preserved while hiding the witness. The central insight is that a random point evaluation of a polynomial acts as a compact fingerprint of the entire polynomial, and putting these together, the verifier's random choices at each round reduce the prover's claim about a complex algebraic expression to a sequence of verifiable assertions about low-degree polynomials. The bridge is that the TQBF characterisation of PSPACE from 47.02.05 and the sum-check protocol combine to give IP = PSPACE, which is dual to the NP characterisation via SAT, and this connection generalises to the entire framework of probabilistically checkable proofs.

Full proof set Master

Proposition 1 (IP within PSPACE). $IP \subseteq PSPACE$ .

Proof. Let $L \in IP$ via verifier $V$ and honest prover $P$ . The interaction tree has depth $m = O (p (n))$ for polynomial $p$ . Define $val (v)$ as the maximum acceptance probability from node $v$ with optimal prover. For leaves: $val (v) \in {0, 1}$ by the verifier's decision. For prover nodes: $val (v) = max_{m} val (v ∥ m)$ . For verifier nodes: $val (v) = E_{r} [val (v ∥ r)]$ .

A PSPACE machine computes $val (root)$ by depth-first traversal: at each node, enumerate all children, recursively compute their values, and combine according to the node type. The recursion depth is $m = O (p (n))$ , and each level stores one node description of size $O (p (n))$ . Total space: $O (p (n)^{2})$ . Accept iff $val (root) \geq 2/3$ . $□$

Proposition 2 (PSPACE within IP). $PSPACE \subseteq IP$ .

Proof. Let $L \in PSPACE$ , so $L$ reduces to TQBF by 47.02.05. Given a QBF $Φ = Q_{1} x_{1} \dots Q_{m} x_{m} \cdot ψ$ , arithmetise $ψ$ into a polynomial $p_{ψ}$ over $F_{q}$ with $q > 2^{m + 2}$ . Define

A = {\prod_{x_{1}} \sum_{x_{2}} \dots using \prod for \forall, \sum for \exists.

The prover claims a value for $A$ . At each quantifier level, apply the sum-check (or product-check) protocol. For a sum $\sum_{x_{i}} f (x_{i})$ , the prover sends the univariate polynomial $h_{i} (x_{i}) = f (x_{i})$ restricted to the random partial assignment. The verifier checks $h_{i} (0) + h_{i} (1)$ matches the previous claim, picks $r_{i}$ at random, and continues. For a product $\prod_{x_{i}} f (x_{i})$ , the prover sends $h_{i}$ and the verifier checks $h_{i} (0) \cdot h_{i} (1)$ .

After $m$ rounds, the verifier evaluates $p_{ψ}$ at the random point $(r_{1}, \dots, r_{m})$ and checks the final polynomial claim. By Schwartz-Zippel, the soundness error per round is $d / q$ where $d \leq poly (n)$ . With $q > 2^{m + 2}$ and $m$ rounds, the total error is at most $m \cdot d / q < 1/3$ . $□$

Proposition 3 (sum-check soundness). In the sum-check protocol, if the prover's claimed total is wrong, the verifier rejects with probability $\geq 1 - n d / q$ .

Proof. At each round $i$ , if the prover's polynomial $h_{i}$ is incorrect (does not equal the true partial sum polynomial $g_{i}$ ), then by Schwartz-Zippel, $h_{i} (r_{i}) = g_{i} (r_{i})$ with probability $\leq d / q$ over the random choice of $r_{i}$ . The error events across rounds are chained: the verifier's check at round $i + 1$ depends on the value set at round $i$ . By a union bound over $n$ rounds, the probability that the prover cheats successfully at every round is at most $n d / q$ . $□$

Proposition 4 (amplification). The completeness and soundness parameters $2/3$ and $1/3$ can be replaced by $1 - 2^{- k}$ and $2^{- k}$ for any polynomial $k$ , with only polynomial overhead.

Proof. Repeat the protocol $O (k)$ times in parallel (or sequentially). The verifier accepts only if all repetitions accept. By a Chernoff bound, completeness drops from $2/3$ to $1 - 2^{- k}$ , and soundness drops from $1/3$ to $2^{- k}$ . The interaction length and verifier time increase by a factor of $O (k)$ . $□$

Connections Master

Space complexity and PSPACE 47.02.05 provides TQBF as the PSPACE-complete problem that is the target of the arithmetisation. The Savitch-style recursive reachability predicate from that unit is the starting point for the QBF encoding used in the IP = PSPACE proof.
The polynomial hierarchy 47.03.01 sits inside PSPACE = IP, so every level of PH has an interactive proof. The relationship between round complexity and hierarchy level is an active research direction.
PCP theorem 47.03.05 is the direct descendant of IP = PSPACE. The arithmetisation and polynomial identity testing developed here become the encoding method for probabilistically checkable proofs.
Zero-knowledge proofs 47.06.03 are interactive proofs with an additional secrecy requirement. The IP = PSPACE theorem shows that interactive proofs are extremely powerful, and zero-knowledge inherits this power for all of PSPACE.
#P and counting 47.02.07 connects to IP through the LFKN theorem that shows #P is within IP. The sum-check protocol was originally developed for verifying counting computations.

Historical & philosophical context Master

The IP = PSPACE theorem was the culmination of a remarkable series of results in the late 1980s. Goldwasser, Micali, and Rackoff (1985) introduced the interactive proof model in the context of zero-knowledge proofs. Babai (1985) independently introduced the Arthur-Merlin model, a public-coin variant. Both models capture the idea of a computationally bounded verifier interacting with a powerful prover.

The sum-check protocol was introduced by Lund, Fortnow, Karloff, and Nisan in their 1990 paper "Algebraic Methods for Interactive Proof Systems," which showed that #P functions could be verified interactively. This was already a breakthrough, as it placed the counting hierarchy within IP. Shamir, in his 1990 paper "IP = PSPACE," extended the LFKN technique to handle alternating quantifiers, completing the characterisation ^{[Arora-Barak §8.3]}.

The result was surprising for two reasons. First, it showed that interaction and randomness are far more powerful for verification than static proofs: IP captures PSPACE, not just NP. Second, it established a deep connection between algebra and logic, showing that Boolean formulas could be "arithmetised" into polynomials and verified using the algebraic properties of finite fields.

Bibliography Master

@article{shamir1990ip,
  author  = {Shamir, Adi},
  title   = {{IP} = {PSPACE}},
  journal = {Journal of the ACM},
  volume  = {39},
  number  = {4},
  year    = {1992},
  pages   = {869--877}
}

@inproceedings{lund1990algebraic,
  author    = {Lund, Carsten and Fortnow, Lance and Karloff, Howard and Nisan, Noam},
  title     = {Algebraic methods for interactive proof systems},
  booktitle = {Proceedings of the 31st Annual Symposium on Foundations of Computer Science},
  year      = {1990},
  pages     = {2--10}
}

@article{goldwasser1989knowledge,
  author  = {Goldwasser, Shafi and Micali, Silvio and Rackoff, Charles},
  title   = {The knowledge complexity of interactive proof systems},
  journal = {SIAM Journal on Computing},
  volume  = {18},
  number  = {1},
  year    = {1989},
  pages   = {186--208}
}

@article{babai1985trading,
  author  = {Babai, L{\'a}szl{\'o}},
  title   = {Trading group theory for randomness},
  journal = {Proceedings of the 17th Annual ACM Symposium on Theory of Computing},
  year    = {1985},
  pages   = {421--429}
}

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009}
}

Prerequisites

47.02.05 pending
47.03.01 pending

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §8.1 (the idea of a verifier interacting with a powerful but untrusted prover, and why this model captures more than NP)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §8.1-8.3 (the class IP, the sum-check protocol, the LFKN theorem, and Shamir's proof that IP = PSPACE)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §8.1-8.4 (full proof of IP = PSPACE via arithmetisation and the sum-check protocol, the LFKN protocol for #P, Shamir's extension to TQBF, and the consequences for the polynomial hierarchy); Babai 1985 trading group theory for probability

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). §8.1 defines the interactive proof model: a probabilistic polynomial-time verifier $V$ interacts with an all-powerful prover $P$ through a polynomial-length exchange of messages, and the completeness and soundness conditions require $Pr [V \leftrightarrow P accepts x] \geq 2/3$ for $x \in L$ and $Pr [V \leftrightarrow P^{*} accepts x] \leq 1/3$ for all provers $P^{*}$ when $x \in / L$ ; §8.2 presents the sum-check protocol of Lund, Fortnow, Karloff, and Nisan (1990) for evaluating $\sum_{x_{1}} \sum_{x_{2}} \dots \sum_{x_{n}} g (x_{1}, \dots, x_{n})$ where $g$ is a polynomial over a finite field, with the prover sending claimed partial sums that the verifier checks by random evaluation; §8.3 gives Shamir's 1990 proof that $IP = PSPACE$ by arithmetising the TQBF formula: each quantifier becomes a sum or product over the field, and the recursive evaluation is verified by the sum-check protocol at each level; §8.4 discusses consequences including $PH \subseteq IP$ and connections to program checking.

Estimated time

beginner: 15m
intermediate: 50m
master: 100m