Motivation
A polynomial-space machine can have exponentially many configurations, so its entire transition matrix is too large for a polynomial-time verifier to write down. The key is to verify one matrix entry by asking for carefully chosen low-degree summaries. Repeated squaring reduces a long computation to shorter ones, while random line checks prevent the number of claims from doubling at every stage.
We prove , and combine it with the polynomial-space upper bound for interactive proofs proved in the quantified-formula companion. The proof uses the sum-check protocol and its adaptive soundness theorem from the companion sum-check unit. It also uses the existence of finite fields of order , polynomial-time arithmetic in an explicitly represented finite field, and standard polynomial-space machine configurations. We explain how the verifier obtains a suitable explicit field below. The proof is conditional on those named foundations, not on an unproved quantum or counting theorem.
Fix a deterministic polynomial-space decider for a language , in a one-work-tape model with a binary work alphabet; standard simulation and binary encoding preserve polynomial space and are used as background. For an input , encode its configurations as -bit strings, with polynomial in . Add an accepting sink and a rejecting sink, each with a self-loop, and redirect halting configurations to the appropriate sink. Add sufficiently many unused bits fixed to zero in every valid encoding so that the number of valid configurations plus sinks is less than . Invalid bit strings have no outgoing edge. Every configuration reachable from the true start has exactly one successor, and the machine eventually reaches one sink.
A Boolean transition matrix and its low-degree extension
Let be the matrix over a finite field whose entry is one exactly when is the designated successor of and zero otherwise. Put
Because the start has a unique successor at every step, the row of indexed by the start has exactly one nonzero entry, equal to one, at the configuration reached after steps. A halting computation cannot repeat a configuration before halting, so by time it has reached a sink. Thus
This uses determinism: a general nondeterministic graph can have many walks, whose count might vanish modulo the field characteristic even when a path exists.
Definition 9.3.1
(Multilinear extension of a transition matrix)
For a bit string , define the equality indicator
At a Boolean point , this is one when and zero otherwise. Extend each matrix to a polynomial in variables by
It agrees with on Boolean pairs and has degree at most one in each variable. Its total degree is at most . The expression has exponentially many terms, so the verifier will not expand it for .
Worked example 9.3.2
(A two-state deterministic transition)
For the transition , , the Boolean matrix is . Its multilinear extension is simply : for either Boolean source, the entry is one exactly when the target bit is one. Squaring the matrix gives the same matrix. This tiny example shows how a polynomial can represent all matrix entries without listing them during verification.
The base extension can be evaluated efficiently for a local configuration encoding. Use one-hot state and head-position bits, binary tape-cell bits, and distinct fixed codes for the two sinks chosen outside the ordinary configuration codes. In every valid ordinary configuration the complete state and each complete head pattern are one-hot, and every unused bit is zero. Enumerate the polynomially many combinations of current nonhalting state, input-head position, work-head position and scanned work symbol. For each legal transition case, multiply indicators fixing the full source and target state/head patterns, all unused bits and the changed tape cell. For every unchanged tape cell with source bit and target bit , use the multilinear equality factor . Each case is a product in which each source or target bit appears in at most one factor.
A transition from a halting configuration to a canonical sink is handled separately: fix the full halting source control and head patterns and unused source bits, but leave the source tape bits unconstrained; multiply by an indicator for the target's entire fixed sink code. Do not impose unchanged-tape equalities in this case, since the canonical sink can have a different tape. Each sink self-loop is represented by the product of the indicators for its full source and target codes. These halting and sink cases are disjoint from the nonhalting cases, and the latter are disjoint on Boolean encodings because the current state, head positions and scanned symbol determine the case. Invalid encodings match no case. The sum has polynomially many cases and is a polynomial-size circuit, multilinear in every source and target bit, agreeing with on Boolean pairs. Uniqueness of multilinear interpolation on the Boolean cube identifies it with .
For the uniqueness claim, if two multilinear polynomials agree on every Boolean input, subtract them and induct on the number of variables: write the difference as with neither coefficient involving . Evaluation at and makes both coefficients vanish on the smaller Boolean cube; induction makes them zero polynomials. Thus the verifier can evaluate the required base extension, not merely an arbitrary polynomial with the same Boolean values.
Worked example 9.3.3
(Equality away from Boolean inputs)
In characteristic two, the multilinear equality polynomial for one bit is . It equals one at Boolean pairs and zero at . Over , however, , which is neither zero nor one. The verifier evaluates the polynomial at field points; it does not pretend that each intermediate value is a Boolean truth value. This behavior is expected and is exactly why the multilinear extension must be specified.
One squaring step as a sum-check
For a bit string and a field vector , the indicator is defined above. When is replaced by a field vector , use its multilinear interpolation in :
For a claimed value of , the matrix-squaring identity gives
Here are fixed field vectors during the sum. Define the summand as a polynomial in field variables by replacing the Boolean strings in that expression with vectors of variables and using .
Proposition 9.3.4
(The squaring summand has small individual degree)
The summand in field variables has degree at most two in each individual variable. Therefore a sum-check with degree bound two reduces a claim about to a claim about that summand at one random triple .
Proof
(Proof)
Each appears in one equality-indicator factor and in the multilinear polynomial , giving degree at most two. The same holds for each . A coordinate appears once in each of the two multilinear matrix factors, again giving degree at most two. The identity follows by expanding the definition of and substituting on Boolean indices. The sum-check theorem applies to this formal low-degree polynomial even though the verifier cannot directly expand it.
At the final sum-check point, the verifier can compute the two equality-indicator factors but cannot yet evaluate . It asks the prover for the two claimed values
and checks that their product, times the known indicator factors, equals the final sum-check claim. These two values are not trusted. Verifying them separately at every squaring level would create a binary tree of claims, so we combine them into one claim.
Combining two claims on a random line
Let and be the two points in . The prover sends a univariate polynomial of degree at most , claiming
The verifier checks and , chooses a fresh uniform and recursively checks the single claim that . A coefficient list longer than is rejected. The true restriction to the line has degree at most because is multilinear in variables.
Proposition 9.3.5
(Random-line claim reduction)
If at least one of is false and the endpoint checks pass, the probability that the recursive claim is nevertheless true is at most .
Proof
(Proof)
The sent polynomial and the true line restriction have degree at most . If either endpoint value is false while the endpoint checks pass, the two polynomials differ at that endpoint and hence are not identical. Their nonzero difference has at most roots in . The prover chooses before seeing the fresh uniform , so even conditioned on the entire preceding transcript, the chance that equals the true value is at most .
Worked example 9.3.6
(A false endpoint on a line)
For a toy multilinear polynomial over , let and . The true line restriction is . If a prover falsely claims the second endpoint is three, any sent with differs from . If the allowed degree is two, the difference can vanish at at most two field elements. The random challenge may miss a particular error, but it cannot hide a false endpoint at every challenge under the stated degree bound.
The complete verification protocol
The verifier starts with the claim and applies the squaring sum-check followed by the random-line reduction for . At level zero it evaluates the polynomial-size circuit for directly. All prover messages have explicitly checked degree bounds.
Theorem 9.3.7
(Polynomial-space languages have interactive proofs)
.
Proof
(Proof)
Choose a field of size . One deterministic way to obtain an explicit field is to choose and enumerate monic binary polynomials of degree until an irreducible one is found, testing candidates by enumerating possible monic factors. There are at most candidates and at most possible factors, so this brute-force construction is polynomial in . Existence of an irreducible polynomial of each positive degree follows from the finite-field construction and the existence of a multiplicative generator; these facts are proved in the finite-field companion. The quotient represents , supports polynomial-time arithmetic, and a uniform -bit string samples a uniform field element.
If , all claimed values can be chosen honestly. The Boolean starting entry is one, each matrix identity and sum-check is exact, and the line restriction passes both endpoints and every challenge. The verifier accepts with probability one.
If , the initial claim is false. At a level , the sum-check uses variables and individual degree two, so its adaptive soundness argument bounds the probability that a false sum claim becomes a true final summand claim by . If the final claim is still false but the prover's product check passes, at least one of must be false: if both were correct, their product and the known indicators would give the true summand value. If an indicator factor is zero, a false nonzero final claim cannot pass that check at all.
With a false endpoint, the line-reduction theorem bounds the chance that the next recursive claim becomes true by . Conditional on every preceding transcript, the probability of escaping a false claim at this level is therefore at most . There are levels. A union bound over the first level at which a false claim becomes true gives total probability at most . If no such escape occurs, the verifier's direct base evaluation rejects. Thus every prover is accepted on a no-instance with probability at most .
There are levels, each with sum-check rounds and one line check. Degree-two messages have three coefficients and line messages have at most coefficients. All field arithmetic, base evaluation, communication and random-bit generation use polynomial resources. The prover is unrestricted and can compute the exponentially large matrix entries and honest message coefficients. This is an interactive proof for .
Proof X-ray
Where the error budget and the claim count come from
Determinism is used once, at the start: it makes equal to zero or one rather than a walk count that could cancel in the field. The one non-obvious move is the line reduction. Each squaring produces two claims, about and about ; checking both separately would leave claims at level , hence claims at level zero and an exponential-time verifier. Merging them on one line leaves exactly one claim per level. The error budget is additive: at most from the sum-check ( rounds, degree two) plus from the random line, so per level and over levels once . The argument closes at level zero: a claim that is still false there is compared with the directly computed value of and rejected. If the field were much smaller, say , the bound would exceed and certify nothing.
Common mistake
(Why the argument uses a deterministic configuration graph)
The matrix entry counts walks in the chosen field. For a nondeterministic graph, the number of accepting walks may be divisible by the characteristic and hence equal zero in the field even when accepting walks exist. For example, if the start has two successors that both move to the accepting sink in the next step, there are two walks of length two from the start to the sink, and in a field of characteristic two. A deterministic space-bounded decider has a unique computation from the start; the absorbing sinks make the relevant entry exactly zero or one, avoiding this cancellation problem.
The polynomial-space upper bound for IP is proved independently in the quantified-formula companion by enumerating public transcripts and counting consistent private random tapes. Combining the two inclusions gives . The proof here uses a local configuration-matrix construction and sum-check; it does not rely on the separate TQBF-to-IP arithmetization route.
Practice and solutions
Quick check
(Why does the start row of have exactly one nonzero entry for the encoded deterministic computation?)
Follow the computation from the start for steps.
Solution · Answer
Each reachable configuration has one successor. Induction on the number of steps gives exactly one walk from the start, and its matrix entry is one; absorbing sinks preserve uniqueness after halting.
Quick check
(Why must the base polynomial be the multilinear extension rather than merely any polynomial agreeing on Boolean points?)
Which degree bound does the random-line step rely on?
Solution · Answer
The random-line restriction must have a known degree at most . An arbitrary agreeing polynomial could contain high-degree terms vanishing on the Boolean cube, invalidating the root bound.
Quick check
(What individual degree bound does the squaring summand have in each ?)
Count the factors in which occurs.
Solution · Answer
At most two: appears in each of two factors, and each factor is multilinear in that variable.
Quick check
(Why does the verifier not recursively check and separately?)
How many claims would there be after levels?
Solution · Answer
Separate recursive checks would double the number of claims at every squaring level. The random-line test reduces the two endpoint claims to one recursively checked claim.
Quick check
(If one endpoint claim is false, why is the line polynomial sent by the prover different from the true line restriction?)
Compare the two polynomials at the false endpoint.
Solution · Answer
The sent polynomial passes both endpoint tests, so it differs from the true restriction at any falsely claimed endpoint. A difference at one point implies the formal polynomials are not identical.
Quick check
(With , what is the upper bound obtained for a false initial claim after levels?)
Add the per-level errors and use the union bound.
Solution · Answer
The union bound gives at most .