Motivation
A quantified Boolean formula describes a game: existential choices try to make the formula true, while universal choices challenge them. Evaluating the game may require exploring exponentially many plays, but a depth-first search can reuse memory. Conversely, a compact quantified formula can describe reachability through an exponentially large configuration graph. These two directions make the problem of deciding true quantified Boolean formulas a natural complete problem for polynomial space.
Definition 3.3.1
(Quantified Boolean formulas and TQBF)
A quantified Boolean formula is built from Boolean variables, connectives and quantifiers ranging over . A closed formula has no free variables. Let TQBF be the language of true closed quantified Boolean formulas under a standard finite encoding. We allow nested quantified formulas, not only formulas already in prenex form. Standard variable-renaming and syntactic encodings can be carried out in polynomial time; the proof below does not rely on moving quantifiers through arbitrary negations.
Evaluation uses polynomial space
Proposition 3.3.2
(TQBF belongs to PSPACE)
TQBF is decidable by a deterministic polynomial-space machine.
Proof
(Recursive evaluation with a reused stack)
Evaluate the formula recursively. At an existential quantifier, evaluate the remaining formula first with the variable set to zero and then, if necessary, with it set to one; return true if either evaluation is true. At a universal quantifier return true only if both evaluations are true. At Boolean connectives evaluate their operands and combine the truth values. Variable names are renamed if necessary so that scopes are unambiguous.
The machine stores the current variable assignments, a pointer into the input formula and a recursion stack of depth at most the formula length. Each stack frame uses polynomially many bits, and finished recursive calls reuse their workspace. The total space is polynomial in the input length. There may be exponentially many recursive calls, so this is a space bound, not a polynomial-time bound.
Worked example 3.3.3
(A two-round quantifier game)
The statement is true: after seeing , choose . Reversing the order gives , which is false because one fixed bit cannot equal both zero and one. A recursive evaluator checks both values of the universal variable and reuses the same memory for the second branch. The example illustrates why later choices may depend on earlier ones.
Describing exponentially long reachability compactly
Suppose vertices of a directed graph are encoded by -bit strings, and a Boolean formula of polynomial size decides whether the encoded vertices have an edge. The graph can have as many as vertices. Define a quantified formula that is true exactly when there is a walk from to of at most edges. Its base case is
The equality case permits a walk of length zero, which is useful when one half of a split is shorter than the other.
The obvious recurrence duplicates the previous formula and can make its written length exponential in . We avoid that duplication with a universal selector bit. Let assert that if and if . It is a Boolean formula of size comparing corresponding bits. Define
where are -bit blocks and is one bit. Each newly bound variable is renamed to avoid capture.
Theorem 3.3.4
(The selector recurrence)
For every , the formula is true exactly when there is a directed walk from to with at most edges. Its written length is polynomial in , and the size of the edge formula.
Proof
(Equivalence and size of the selector formula)
The base case allows a zero-edge walk or one edge. For the induction step, suppose a walk of length at most exists. Choose at a point splitting it into two walks of length at most ; an empty half is allowed. For each value of , choose the uniquely forced pair corresponding to one half. The induction hypothesis makes the recursive formula true, so is true.
Conversely, if is true, its chosen must work for both values of . The selector forces the recursive pair to be for zero and for one. The induction hypothesis gives a walk of length at most for each half. Concatenating them gives a walk of length at most .
The displayed formula contains only one copy of . Each wrapper adds symbols, apart from standard variable-name encoding overhead. Thus its size after levels is polynomial in and the base edge formula. The alternating selector replaces syntactic duplication with quantifier choices; it does not claim that evaluating the formula takes polynomial time.
Proof X-ray
How the selector keeps the formula short
The naive recurrence contains twice, so its length doubles at every level and reaches times the base size after levels. The selector formula contains once and hands it the pair that the universal bit selects, so the length grows by only per level. The equivalence proof uses the quantifier pattern in both directions: the midpoint is fixed before , so one must serve both halves, and is universal, so both halves are genuinely required. The existential are not real choices, since for each the selector forces them. Nothing here makes evaluation fast: the formula describes an exponentially long search that the polynomial-space evaluator still has to carry out.
Worked example 3.3.5
(A two-edge walk)
For a graph with edges and , the formula can choose the midpoint . If the universal selector chooses zero, the forced recursive query is ; if it chooses one, it is . Both are true. If only is present and no other path to exists, the second selector choice exposes the missing half and rejects that midpoint.
Common mistake
(A universal selector does not choose the midpoint)
The midpoint is existentially chosen before the universal bit. It must work for both halves. If the quantifiers were reversed, , the two branches could use unrelated midpoints, and the two short walks might not concatenate. The positions of the quantifiers are part of the reachability proof.
Counterexample mode
Reversing the midpoint and selector quantifiers
Suppose the pattern is replaced by , so that the midpoint may depend on the selector bit. Take a graph with edges , , , , two disjoint paths, so is not reachable from . For the reversed formula needs a with a walk of at most two edges from to , and works. For it needs a with a walk of at most two edges from to , and works. The reversed formula is therefore true although is unreachable. With the correct order a single must be reachable from within two edges and reach within two edges; the first set is and the second is , so no such exists and the formula is false, as it should be.
PSPACE-hardness of TQBF
Theorem 3.3.6
(TQBF is PSPACE-complete)
Every language in PSPACE reduces to TQBF by a polynomial-time many-one reduction. Together with membership, TQBF is PSPACE-complete under such reductions.
Proof
(Encoding a space-bounded computation)
Fix a deterministic polynomial-space decider for a language . On an input of length , encode a complete configuration by bits for a polynomial : include the finite state, input-head position, work-head positions and the polynomially bounded work-tape contents. Enlarge if needed to reserve a distinct accepting sink. There are at most candidate bit strings. The actual start configuration and the sink have explicit encodings computable from .
A polynomial-size Boolean formula tests whether is a legal one-step successor of , with an edge from each accepting configuration to the fresh sink. To see the size bound, enumerate the polynomially many possible head positions and finitely many states and transition rules. For each case, compare the relevant input symbol, require the prescribed state and head updates, require the one changed work cell to have its new symbol, and require all other work cells to remain unchanged. A disjunction of these polynomial-size cases gives the formula; invalid candidate encodings have no outgoing edges. The input is hardwired into this construction.
Since halts, it accepts exactly when the sink is reachable from its start. Any reachable vertex has a simple path from the start: delete loops between repeated vertices. With at most candidate vertices, a simple path to the sink uses fewer than edges. By the selector theorem, the closed quantified formula is true exactly in this case. Its size and construction time are polynomial in because and are polynomial. Therefore if and only if the produced quantified formula is true.
The reduction includes syntactically possible but unreachable configurations. That does not create a false accepting path: every edge from a reachable configuration is an actual transition, so induction on path length keeps the entire path within genuine computations. The fresh sink permits multiple accepting configurations without requiring the formula to guess which one will be reached.
Simulating an interactive proof in polynomial space
Definition 3.3.7
(Interactive proof)
An interactive proof has a polynomial-time randomized verifier and an unrestricted prover. Completeness requires some prover to make the verifier accept a yes-instance with probability at least ; soundness bounds the acceptance probability of every prover by on a no-instance. The verifier's time, number of random bits, number of messages and permitted message lengths are polynomially bounded for every transcript. This includes private randomness.
Theorem 3.3.8
(Interactive proofs lie in PSPACE)
.
Proof
(Enumerating public transcripts)
Fix an input. Pad the verifier's random tape to a fixed polynomial length and the interaction to a fixed polynomial number of public message rounds, using explicit padding after early termination. A prover sees the verifier's public messages, not its private random tape. We enumerate a tree of public transcripts, not a tree that reveals hidden random choices to the prover.
At a prover-message node, enumerate all permitted next messages and take the maximum continuation count. At a verifier-message node, sum the continuation counts over all possible next public messages and terminal outcomes. At a leaf, the transcript fixes all prover messages and all public verifier messages. Enumerate the private random tapes, replay the deterministic verifier with those prover messages, and count the tapes that produce exactly the recorded public transcript and accept. This count fits in bits. Invalid or inconsistent transcripts contribute zero.
The recursion computes the maximum number of accepting random tapes attainable from each public history. Verifier-message branches partition the consistent private tapes, so their counts add. A prover's next message is chosen from the public history; taking a maximum at that node represents every deterministic strategy without allowing it to depend on hidden coins. A randomized prover cannot improve the maximum because its choices are averages of deterministic continuations. A single deterministic maximizing strategy exists by selecting a maximizing message at each public history in the finite tree.
Each recursion frame stores the public transcript so far, a message-enumeration counter and an -bit accumulator or maximum. The recursion depth is polynomial, and the verifier simulation for a leaf uses polynomial space; finished branches reuse their memory. The number of branches and random tapes may be exponential, but simultaneous storage is polynomial. At the root, divide the maximum accepting-tape count by conceptually and compare it with . Completeness puts it at least on yes-instances, while soundness puts it at most on no-instances. Hence a deterministic polynomial-space machine decides the language.
Worked example 3.3.9
(Maximizing before averaging)
Suppose the prover first sends one bit , after which the verifier flips a fair bit and accepts exactly when . Each fixed message succeeds with probability , so the maximum is . If the verifier instead reveals before the message, the prover can choose and the maximum becomes one. The public-transcript evaluator respects this order: it maximizes only after messages the prover actually sees, while it counts private random tapes at the leaves. If is secret, maximizing separately after learning its value would incorrectly give the prover hidden information.
The reverse inclusion requires an interactive protocol for a PSPACE-complete problem such as TQBF. The companion sum-check unit proves a low-degree sum protocol, but additional arithmetization and degree-control arguments are required to turn quantified formulas into such an interactive proof. They are not proved here. Therefore this unit establishes TQBF completeness and the IP upper bound, not the full equality .
Practice and solutions
Quick check
(Why can a depth-first quantified-formula evaluator use polynomial space despite exploring exponentially many assignments?)
Solution · Answer
It stores only the current assignment and recursion stack, and reuses that space after finishing each branch. The number of branches affects time but need not affect simultaneous storage.
Quick check
(In the selector recurrence, why must the midpoint be chosen before the universal selector bit?)
Solution · Answer
The same midpoint must split the walk for both selector values. Choosing it later could permit unrelated midpoints and would not guarantee a concatenated path.
Quick check
(If a graph has at most encoded vertices, what is a sufficient simple-path length bound?)
Solution · Answer
A reachable vertex has a simple path with at most edges; allowing edges is a convenient sufficient bound.
Quick check
(Why does the selector recurrence have polynomial written size while the naive two-copy recurrence may not?)
Solution · Answer
Each selector wrapper contains only one copy of the previous formula and adds polynomially many symbols. The naive recurrence contains two copies at each level, so its written size can double repeatedly.
Quick check
(At a prover node in the interaction-tree simulation, why is taking a maximum sufficient?)
Solution · Answer
For each possible message the continuation has a well-defined acceptance probability. A randomized choice averages those values and cannot exceed their maximum; a maximizing deterministic choice exists because the message set is finite.
Quick check
(Does the proof of establish the reverse inclusion?)
Solution · Answer
No. The reverse direction needs a separate interactive protocol for a PSPACE-complete language, including arithmetization and degree-control work not proved here.