title: "Lecture 18 - PSPACE and Savitch's Theorem"
unit: 3
lecture: 18

Lecture 18 - PSPACE and Savitch's Theorem

(Skeleton for Fall 2026.)

PSPACE

TODO: definition; TQBF as the canonical PSPACE-complete problem; games as the intuition (quantifier alternation is adversarial play).

Savitch's Theorem

TODO: NSPACE(f(n)) inside SPACE(f(n)²); the reachability-by-recursion proof; corollary PSPACE equals NPSPACE, and why the time analogue is wide open.

PSPACE-Completeness

TODO: TQBF completeness proof sketch; generalized games (mention: Go, geography) as PSPACE-complete territory.