PSPACE-Completeness

A language $L$ is PSPACE-complete if (1) $L \in \text{PSPACE}$, and (2) every language $A \in \text{PSPACE}$ satisfies $A \le_p L$, meaning there is a polynomial-time computable function $f$ such that $x \in A \iff f(x) \in L$. This is a polynomial-time many-one reduction, exactly as in NP-completeness — the reduction itself must run fast, even though the problems it relates may require large space and correspondingly large time. Completeness under polynomial-time reductions is the right notion because PSPACE is closed under polynomial-time reductions: composing a polynomial-time reduction with a polynomial-space decision procedure still uses only polynomial space (the reduction's output has size polynomial in the input, so feeding it to a poly-space machine still costs polynomial space overall). The centerpiece example is TQBF, the language of true fully-quantified Boolean formulas. A quantified Boolean formula (QBF) has the form

where each $Q_i \in \{\exists, \forall\}$ and $\phi$ is a quantifier-free Boolean formula (typically in CNF) over variables $x_1, \ldots, x_n$. Since every variable is quantified, $\Phi$ has a fixed truth value — no free variables remain — and TQBF asks: is that value true? This generalizes SAT (which only has $\exists$ quantifiers) to arbitrary alternation of $\exists$ and $\forall$, and this alternation is exactly what encodes adversarial, game-like structure: "$\exists$ a move $x_1$ such that $\forall$ opposing replies $x_2$, $\exists$ a counter-move $x_3$..." A QBF with $k$ quantifier alternations is naturally interpreted as a $k$-round two-player game where the existential player tries to satisfy $\phi$ and the universal player tries to falsify it. The reason TQBF captures all of PSPACE is structural: a polynomial-space Turing machine's configuration (tape contents, head position, state) can be described using only polynomially many bits, since space is polynomially bounded. The set of all possible configurations therefore has size at most exponential in the input length, but each individual configuration is describable in polynomial space. Reachability between configurations — "can configuration $c_1$ reach configuration $c_2$ in at most $t$ steps" — is expressible as a quantified Boolean formula whose size grows only polynomially in $\log t$ via a halving trick, even though $t$ itself may be exponential. This is precisely the technique underlying Savitch's Theorem, and the TQBF completeness proof reuses it directly.

We prove TQBF is PSPACE-complete in two parts: membership (TQBF $\in$ PSPACE) and hardness (every PSPACE problem reduces to TQBF).

Membership. A QBF with $n$ variables and $k$ alternating quantifier blocks can be decided by recursively branching on each quantified variable's two possible truth assignments, reusing space between recursive calls. The recursion depth is $n$ (one level per variable), and each level needs only enough space to remember the current partial assignment and a return address — polynomial overhead per level — giving polynomial total space, even though the time used is exponential (the recursion tree has up to $2^n$ leaves).

Hardness — the key construction. Let $A$ be any language decided by a deterministic Turing machine $M$ using space $s(n) = n^k$ for some constant $k$, on inputs of length $n$. We build, in polynomial time, a QBF $\phi_x$ such that $x \in A \iff \phi_x$ is true. Fix input $x$ of length $n$. Every configuration of $M$ on input $x$ — tape contents on the used portion of the tape, head position, and control state — can be encoded as a binary string of length $O(s(n))$, since the tape is bounded by $s(n)$ cells (each with a bounded alphabet), the head position needs $O(\log s(n))$ bits, and the state needs $O(1)$ bits. Let $c_{\text{start}}$ be the encoding of $M$'s start configuration on $x$, and $c_{\text{accept}}$ a canonical accepting configuration (we may assume $M$ has a unique accepting configuration by clearing the tape and halting in a fixed state before accepting). Because $M$ uses space $s(n)$, it has at most $2^{O(s(n))}$ distinct configurations, so if $M$ accepts $x$ at all, it accepts within $T = 2^{O(s(n))}$ steps (else it would repeat a configuration and loop forever, contradicting that it halts on all inputs — we assume WLOG $M$ always halts). We want to express "$c_{\text{start}}$ can reach $c_{\text{accept}}$ in at most $T$ steps" without writing down a formula of length $T$. Define the predicate

The naive recursive definition

halves $t$ at each level of recursion (so only $\log T = O(s(n))$ levels are needed), but naively expanding it duplicates the REACH subformula twice at each level, causing exponential blowup after $O(s(n))$ levels. The fix — the same one used in Savitch's Theorem — is to share the two recursive calls using a universally quantified formula that forces both to use the same smaller formula:

Here $(a,b)$ ranges over only two possible pairs, expressed with a universal quantifier over a single bit selecting which pair, plus an implication that checks the selected pair against the recursive formula. This keeps the formula size roughly constant per level of recursion instead of doubling, so after $\log T = O(s(n))$ levels the total formula size is $O(s(n)^2)$ — polynomial. ``` // Reduction: poly-space TM M on input x → QBF φ_x with φ_x true iff M accepts x function REDUCE-TO-TQBF(M, x): n ← |x| s ← space bound of M on inputs of length n // s(n), polynomial T ← 2^(c·s) // upper bound on steps, c a constant c_start ← encoding of M's initial configuration on x c_accept ← encoding of the canonical accepting configuration // Base case formula: "c1 = c2, OR c1 yields c2 in exactly one M-step" function PHI_STEP(c1, c2): return (c1 == c2) OR (c2 is a valid successor configuration of c1 under M) // both checks are expressible as poly-size quantifier-free Boolean formulas // over the bits encoding c1 and c2 // Recursive formula builder with variable-sharing trick function PHI_REACH(c1, c2, t): if t == 1: return PHI_STEP(c1, c2) else: let m be a fresh block of variables encoding a configuration let (a, b) be a fresh pair of variables encoding a configuration-pair selector return ∃m. ∀(a, b). [ ((a,b) == (c1,m)) OR ((a,b) == (m,c2)) ] ⇒ PHI_REACH(a, b, t/2) // recursive call is written ONCE in the pseudocode, // but a and b are bound variables reused for both branches φ_x ← PHI_REACH(c_start, c_accept, T) return φ_x ``` Notice the crucial economy: `PHI_REACH` is called recursively exactly once per level (not twice), because the universal quantifier over $(a,b)$ forces the single sub-formula to be checked against both possible configuration pairs. Expanding the recursion literally would double the formula at each level; quantifying over the choice instead keeps growth additive. This is the entire trick, and it is what makes the reduction run in polynomial time and produce a polynomial-size formula. Finally,

after substituting in the concrete bit-strings for $c_{\text{start}}$ and $c_{\text{accept}}$, and quantifying all remaining free variables appropriately (existential for configuration-guess variables, universal for selector variables) in the correct nested order, is a valid QBF, computable from $x$ in time polynomial in $n$ (since $T$ has only $O(s(n))$ bits, and the whole formula has $O(s(n)^2)$ variables and clauses).

To finish the hardness proof: since $M$ decides $A$, we have $x \in A \iff M$ accepts $x$ $\iff$ configuration $c_{\text{start}}$ reaches $c_{\text{accept}}$ within $T$ steps $\iff$ $\phi_x$ is true. The map $x \mapsto \phi_x$ runs in time polynomial in $n$ (building $O(s(n))$ nested quantifier blocks, each of size $O(s(n))$, giving total size and construction time $O(s(n)^2)$, which is polynomial since $s(n)$ is polynomial). Hence $A \le_p \text{TQBF}$ for an arbitrary PSPACE language $A$, establishing TQBF is PSPACE-hard, and combined with membership, PSPACE-complete.

Membership time/space. The recursive QBF evaluator branches on $n$ variables, giving $O(2^n)$ time in the worst case, but reuses the same stack space across recursive calls: at any moment the recursion stack holds at most $n$ frames, each storing $O(n)$ bits (current partial assignment plus bookkeeping), for total space $O(n^2)$ — polynomial. This mirrors exactly how a poly-space machine can simulate exponential-time exploration: time can be exponential, but space stays polynomial because space is reused, not accumulated, across branches.

Reduction time/space. The reduction constructs $O(s(n))$ nested levels (since $T = 2^{O(s(n))}$ and each level halves the exponent), and each level contributes $O(s(n))$ new variables and a quantifier-free formula of size $O(s(n))$ describing valid transitions — giving total formula size $O(s(n)^2)$, and construction time polynomial in $n$ for any fixed polynomial $s(n)$. This is the crux of why the reduction is efficient despite encoding a computation that may take doubly-exponential time in $n$ to actually run.

Correctness invariant. The induction is on $t$: PHI_REACH$(c_1, c_2, t)$ is true if and only if $M$'s configuration $c_1$ can reach configuration $c_2$ within $t$ steps.

• Base case ($t = 1$): PHI_STEP$(c_1, c_2)$ directly checks equality or single-step transition validity, which is exactly "reachable in $\le 1$ step."
• Inductive step: assume PHI_REACH$(\cdot,\cdot,t/2)$ is correctly true iff reachability holds within $t/2$ steps. Then $c_1$ reaches $c_2$ within $t$ steps iff there is some midpoint configuration $m$ with $c_1 \to m$ within $t/2$ steps and $m \to c_2$ within $t/2$ steps. The formula asserts exactly this: $\exists m$ such that for the two selector cases $(c_1, m)$ and $(m, c_2)$, the shared sub-formula (which by induction hypothesis correctly tests reachability within $t/2$ steps) holds. Since the universal quantifier ranges over exactly these two labeled cases (not an arbitrary large domain), correctness transfers without changing the sub-formula's meaning.

By induction on $\log_2 T$ levels, PHI_REACH$(c_{\text{start}}, c_{\text{accept}}, T)$ is true iff $M$ accepts $x$ within $T$ steps, and since $T$ exceeds the total number of configurations, this is iff $M$ accepts $x$ at all.

Honest tradeoffs. PSPACE-completeness under polynomial-time reductions is the standard notion, but because PSPACE already contains problems believed to require exponential time, one might ask whether a weaker reduction (e.g., logspace reductions) still works — and indeed it does; the TQBF reduction above can be implemented in logspace, giving the stronger statement that TQBF is PSPACE-complete under $\le_{\log}$ reductions. This matters because it rules out a subtle circularity: using polynomial-time reductions when the target class itself might not properly contain P would be suspicious, but PSPACE-completeness under logspace reductions is unconditionally meaningful since $L \subseteq P \subseteq \text{PSPACE}$ is a strict hierarchy of inclusions known to hold (though not all strictly, unconditionally). It remains a major open problem whether $P = PSPACE$; PSPACE-complete problems are widely conjectured to require exponential time, consistent with $P \ne PSPACE$, but no proof exists. What is known unconditionally, via a diagonalization argument (the space hierarchy theorem), is that $PSPACE \ne EXPSPACE$, giving at least one guaranteed separation nearby.

Consider the tiny QBF

We evaluate it with the recursive membership algorithm, branching on each variable in order and reusing space between branches.

Both choices of $x_1$ (T and F) make the inner $\forall x_2\,\exists x_3(\cdots)$ false, so $\exists x_1(\cdots)$ is false: $\Phi$ is false. This traces exactly how the recursive evaluator reuses the same $O(n)$-sized stack frame across all $2^3 = 8$ leaf assignments — at no point do we store more than the current path's partial assignment, illustrating polynomial space despite exponential-time branching. Now connect this to the reduction: if $\phi$ above were instead produced by REDUCE-TO-TQBF from some poly-space machine $M$ and input $x$ (with $x_1$ representing an existential "move," $x_2$ a universal "adversary response," and $x_3$ an existential "counter-move," each block corresponding to one halving-step of the REACH recursion), then $\Phi$ being false tells us immediately that $M$ does not accept $x$ — without ever simulating $M$ directly, only by evaluating the quantified formula that encodes its reachability structure.

The concept of quantified Boolean formulas as a complete problem for PSPACE emerged from the broader development of computational complexity theory in the early 1970s, building directly on the reduction techniques pioneered for NP-Completeness by Cook and Karp, and on the space-bounded simulation results established by Savitch.

PSPACE-completeness governs the theoretical difficulty of a wide range of practically important problems. Formal verification of hardware and software model checking often reduces to deciding quantified temporal logic formulas, whose complexity mirrors TQBF's quantifier alternation; industrial model checkers must therefore rely on heuristics and abstraction rather than worst-case-optimal algorithms. Two-player game analysis — deciding whether a position in generalized geography, Hex on an $n \times n$ board, or various board-game generalizations is a forced win — is PSPACE-complete, explaining why perfect play cannot be computed efficiently for large boards even though each individual move is easy to enumerate. AI planning with adversarial or nondeterministic action models (conditional planning, contingent planning) is PSPACE-complete in its general quantified form, motivating the search for restricted planning fragments that fall back into NP or P. More foundationally, TQBF and its completeness proof are the launching point for two major theoretical developments explored elsewhere: The Polynomial Hierarchy, whose levels are defined by bounding the number of quantifier alternations (rather than allowing arbitrarily many, as TQBF does), and Interactive Proofs: An Introduction, where the celebrated result $\text{PSPACE} = \text{IP}$ shows that every PSPACE language — TQBF included — has an efficient interactive proof system, giving a completely different, probabilistic lens on why quantifier alternation is tractable to verify even when it is intractable to decide directly.

Ask the tutor: How does the proof that PSPACE = IP use the same quantifier-alternation structure found in TQBF, and why does that let a verifier check PSPACE statements using only randomness and polynomial time?