PSPACE: beyond NP

Generalized chess on an n x n board is PSPACE-complete. So is generalized Go. So is checking whether a regex with backreferences matches a string. PSPACE is the complexity class above NP, where 'is there a solution' becomes 'is there a winning strategy against an adversary.' The 1970 result that PSPACE = NPSPACE - that nondeterminism does not help when space is the resource - is one of the cleanest proven separations in complexity theory.

• **Game AI**: optimal play in generalized board games is PSPACE-complete - solving them precisely requires polynomial space at minimum
• **Regex backtracking**: regex with backreferences (Perl-compatible) can require exponential time on adversarial inputs - the underlying problem is PSPACE-hard
• **Planning**: classical planning problems with universal goals (FORALL) live in PSPACE - PDDL planners use SAT-modulo-theory backends to scale
• **Verification**: model-checking temporal logic formulas on finite-state systems is PSPACE-complete - tools like SPIN exploit this complexity bound

Historical context

In 1970, Walter Savitch at UC San Diego proved that nondeterministic polynomial space and deterministic polynomial space are equivalent (NPSPACE = PSPACE). The proof introduced the REACH algorithm - a recursive reachability test that trades exponential time for quadratic space by solving each half of the path independently and reusing the stack frame. This result showed that space is fundamentally more reusable than time: a space cell can be written and reused, but a time step cannot be reclaimed. The question of whether P = NP remains unsolved, but Savitch's theorem demonstrates that the analogous question for space is already answered.

QBF: Quantified Boolean Formula

**QBF (Quantified Boolean Formula)** extends SAT by allowing both existential (EXISTS) and universal (FORALL) quantifiers over boolean variables. SAT asks: does there exist an assignment making phi true? QBF asks: is the formula true for all possible assignments of FORALL-quantified variables, given optimal choices for EXISTS-quantified variables? The FORALL quantifier introduces an adversarial dimension - the formula must hold even for the worst-case assignment.

**QBF as a two-player game**: EXISTS quantifiers represent one player (MAX) choosing variable values; FORALL quantifiers represent the opponent (MIN). QBF is true if and only if MAX has a winning strategy regardless of MIN's choices. This game-theoretic view directly connects QBF to two-player perfect-information games like chess and Go.

TQBF: the PSPACE-complete problem

**TQBF (True QBF)** - the problem of deciding whether a given QBF is true - is the canonical PSPACE-complete problem. The recursive EVAL algorithm solves it using O(n) stack space (one frame per variable) but O(2^n) time (exploring all branches). PSPACE is defined by the space bound, not the time bound - using O(n) space puts TQBF in PSPACE even though the time is exponential.

**Why TQBF is PSPACE-complete (not just in PSPACE)**: every problem in PSPACE can be reduced to TQBF in polynomial time. The reduction encodes a computation as a game tree - the existential player models nondeterministic choices, the universal player ensures the reduction is valid for all inputs. This completeness makes TQBF the 'hardest problem in PSPACE.'

PSPACE and game theory

Two-player perfect-information games with alternating moves have a natural correspondence to QBF: EXISTS quantifiers model one player's choices, FORALL quantifiers model the opponent's. The question 'does the first player have a winning strategy?' is equivalent to evaluating a QBF. This places many classic games in PSPACE when generalized to n x n boards.

**Why 8x8 chess is not PSPACE-complete**: computational complexity measures hardness as a function of input size n. Standard 8x8 chess has a fixed board - it is a problem of constant size, and any constant-size problem is in P (solvable by a lookup table). Only when generalized to n x n boards does the complexity become PSPACE-complete. Chess endgame tablebases for up to 7 pieces have been solved by exhaustive computation - a constant-size instance.

Savitch's theorem: NPSPACE = PSPACE

**Savitch's theorem** (1970) states: NPSPACE ⊆ DSPACE(f(n)^2). For polynomial f(n), this means NPSPACE = PSPACE. The proof constructs a deterministic algorithm that simulates nondeterministic space using quadratic space overhead. The key insight: **space can be reused**. When verifying whether a target configuration is reachable, the algorithm needs only the midpoint configuration - not the full path.

**Why the same trick fails for time**: Savitch's proof works for space because an algorithm can overwrite and reuse memory. Time does not have this property - a time step, once spent, is gone forever. The computation of REACH(C_start, C_mid, t/2) and REACH(C_mid, C_accept, t/2) can reuse the same space, but the time spent on both halves accumulates. This asymmetry explains why P vs NP remains unsolved while PSPACE = NPSPACE is proven.

Key Takeaways

• **QBF**: Quantified Boolean Formula extends SAT with FORALL - the formula must hold against an adversary
• **TQBF** (deciding whether a QBF is true) is PSPACE-complete - any PSPACE problem reduces to it
• **Recursive EVAL**: O(n) stack space, O(2^n) time - PSPACE allows exponential time as long as space stays polynomial
• **Games**: two-player perfect-information games on n x n boards are PSPACE-complete; fixed-size 8x8 chess is in P
• **Savitch's theorem (1970)**: NPSPACE = PSPACE - space is reusable in a way that time cannot be

Related Topics

Topics that build on or extend PSPACE Complexity:

• NP-Completeness — Prerequisite to PSPACE - SAT and Cook-Levin theorem set up the techniques used for TQBF completeness
• Generalized Games — Hex, Go, and chess on n x n boards are canonical PSPACE-complete problems
• EXPTIME and Beyond — PSPACE is contained in EXPTIME - the next rung when even polynomial space is insufficient

Вопросы для размышления

• Why does Savitch's REACH algorithm work for space but no analogous trick exists for time? What property of memory does the proof rely on?
• TQBF is PSPACE-complete and 8x8 chess is in P. Where exactly does the constant-vs-parameterized distinction sit in complexity theory?
• If P = NP turned out to be true, would PSPACE collapse with NP? What additional information does the FORALL quantifier provide that EXISTS does not?

Связанные уроки

• cplx-03 — NP-completeness and SAT are prerequisites for understanding PSPACE and TQBF
• comp-04-interpreter-vs-compiler — PSPACE algorithms reuse space like bytecode reuses registers - the key insight is that memory can be freed and reused, unlike time
• gd-04 — Generalized board games (Go, Hex on n x n) are PSPACE-complete - optimal play requires polynomial space
• ds-04-clocks — Savitch's theorem and Lamport clocks share a structural insight: reachability without storing the full history
• cplx-05 — PSPACE and EXPTIME are the next rungs in the complexity hierarchy above NP
• fl-27-p-np
• fl-28-np-completeness
• fl-29-space-complexity
• comp-04
• fl-22-decidability
• alg-02-space