2.1 PSPACE — polynomial memory, unlimited patience
PSPACE = problems decidable using polynomial space (memory), with no time restriction. NPSPACE = the non-deterministic version — but by Savitch's theorem (Unit 2), NPSPACE = PSPACE.
The known chain (memorise; only P ≠ EXP is proved strict):
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ NEXP ⊆ EXPSPACE
└────── P ≠ EXP and NL ≠ PSPACE by hierarchy theorems ──────┘Why NP ⊆ PSPACE: try all 2ⁿ certificates one at a time, reusing the same polynomial workspace — exponential time, polynomial space. Space's reusability is the asymmetry behind this whole lesson.
2.2 TQBF — the PSPACE-complete flagship
TQBF (True Quantified Boolean Formula): is a fully quantified formula like ∀x ∃y ∀z φ(x,y,z) true?
SAT is the special case with only ∃ quantifiers; alternating ∀/∃ is what pushes the problem up from NP to PSPACE-completeness (every PSPACE problem ≤ₚ TQBF — proved by a Savitch-style "reachability through a guessed midpoint" formula construction).
The deep reading — quantifier alternation = game play: ∃y... is a move by a player trying to make φ true; ∀x... is the adversary. TQBF asks: does the ∃-player have a winning strategy? Hence:
PSPACE is the complexity class of perfect-play in games. Generalised versions of hex, Othello, and checkers/Go (with suitable rules) are PSPACE-hard or beyond; "does this position win?" is a quantified-formula question. NP asks for a solution; PSPACE asks for a strategy — an object that answers every counter-move.
2.3 The exponential classes — beyond polynomial time
| Class | Definition | Example inhabitant |
|---|---|---|
| EXP | time 2^poly(n) | generalised chess on n×n boards (EXP-complete) |
| NEXP | non-deterministic 2^poly(n) | succinctly-encoded graph problems |
| EXPSPACE | space 2^poly(n) | equivalence of regular expressions with squaring (EXPSPACE-complete) |
| 2-EXP, ... | 2^2^poly(n), towers... | Presburger arithmetic decision (2-EXP) |
| ELEMENTARY and beyond | any tower height | — and still decidable! |
The hierarchy theorems (diagonalisation, Unit 2) prove these rungs are genuinely distinct: more time/space = strictly more problems. EXP-complete problems are provably outside P — unconditional intractability, no conjecture needed. That's the difference in epistemic status: NP-complete = "hard unless the world surprises us"; EXP-complete = "hard, full stop".
2.4 Below P — the small classes (for the full map)
- L (log space): undirected graph connectivity is here (Reingold 2005 — a celebrated result).
- NL (non-deterministic log space): directed s-t reachability is NL-complete; NL = co-NL (Immerman–Szelepcsényi — non-determinism symmetric for space, another contrast with time!).
- Whether L = P is open — yet another unresolved adjacent pair.
2.5 The complete map
Every arrow is ⊆; dashed = leaving computability altogether. Locating a new problem on this map — which rung, complete for it? — is the discipline's core skill, and a one-mark-per-row exam table.
2.6 PSPACE-completeness, defined properly
L is PSPACE-complete iff (1) L ∈ PSPACE and (2) every A ∈ PSPACE satisfies A ≤ₚ L. The reductions still run in polynomial time — same architecture as NP-completeness, one level up; TQBF plays the role SAT plays for NP.
TQBF ∈ PSPACE: evaluate the quantifier tree recursively — for each quantified variable try x = 0 and then x = 1, reusing the same workspace for both sub-evaluations. Recursion depth n, each frame polynomial → polynomial space (and exponential time — that is the trade space-bounded computation makes).
TQBF is PSPACE-hard (idea): encode "the poly-space machine accepts x" via Savitch's midpoint trick — REACH(C₁, C₂, k) becomes a quantified formula in which a ∀ over the two half-paths lets one shared subformula serve both halves; naive expansion would double the formula at each level, the quantifier keeps it polynomial. That re-use-by-quantifier is the proof's whole cleverness.
2.7 Worked TQBF evaluations (tiny but illustrative)
| Formula | Value | Why |
|---|---|---|
| ∀x ∃y (x ≠ y) | TRUE | whatever x is chosen, y takes the other value |
| ∃y ∀x (x ≠ y) | FALSE | y is fixed first; the adversary x simply copies it |
| ∀x ∃y (x ∨ y) | TRUE | for x = F pick y = T; for x = T anything works |
| ∃x ∀y (x ∨ y) | TRUE | x = T wins regardless of y |
Rows 1–2 are the marks-bearing pair: quantifier order matters — "every position has a reply" is not "one move beats everything". That is precisely the game-theoretic content of TQBF.
2.8 Puzzles vs games — the solution/strategy distinction
| Question type | Logical form | Typical class |
|---|---|---|
| "Is there a solution?" (puzzle) | ∃ certificate | NP — SAT, Sudoku, HAM-CYCLE |
| "Is there a winning strategy?" (game) | ∃ move ∀ reply ∃ move ... | PSPACE — TQBF, generalised hex |
| "Win a game allowing exponentially long play?" | alternation + long horizon | EXP — generalised chess, checkers |
A strategy is a tree of answers to every counter-move, not a single object — that quantifier alternation is the formal content of "games are harder than puzzles".
2.9 Why "polynomial space" is so much bigger than it sounds
A poly-space machine may run for 2^poly(n) steps before halting (the configuration-count bound): it can afford exhaustive search with rewinding — try every certificate, every game line, erase, repeat. That is why NP and co-NP both fit inside PSPACE with no tension at all between "guess a YES proof" and "refute every NO proof": space erases, time cannot. When asked to "compare NP and PSPACE", lead with that sentence.
Exam pointer
① "Define PSPACE and PSPACE-completeness; give a complete problem" — §2.1, §2.6, TQBF. ② "Show NP ⊆ PSPACE" — the certificate-recycling argument of §2.1 in two sentences. ③ "Short note: complexity of games" — §2.2's strategy reading plus §2.8's table. ④ "Draw the class hierarchy and mark what is proved strict" — the mermaid map plus "only P ≠ EXP and the space-hierarchy gaps are proved".
Self-check
- Define PSPACE-completeness. Which resource is bounded in the reduction — time or space?
- Evaluate ∃x ∀y (x ≠ y) and phrase the answer in terms of moves.
- Why is SAT exactly the ∃-only special case of TQBF, and what changes when ∀ enters?
- Prove NP ⊆ PSPACE in two sentences.
- State Immerman–Szelepcsényi (NL = co-NL) and the contrast it draws with the still-open NP vs co-NP question.