Savitch's theorem visualized as a recursion tree, and games that are provably hard to play perfectly.
BCS 402 · Dr. Arash Kermani · CUD
🎧 Narration
🔊 Diagram
A TQBF formula is true iff there is a winning strategy for the existential player in this game tree. ∃ nodes are OR, ∀ nodes are AND. Polynomial depth, exponential tree — depth-first evaluation needs only polynomial space.
1 · Time vs. space
🔊 Diagram
Roughly: space ≤ time, but time ≤ 2^O(space). Polynomial time fits inside polynomial space; polynomial space gives exponential time. The diagonal of complexity is dominated by these two trade-offs.
Space complexity counts the number of tape cells a TM uses. The classes are defined just like
time:
🔊 Formula
SPACE(f(n)) = { L : L decided by some TM using O(f(n)) cells }
PSPACE = ⋃k SPACE(nk)
The key relationship to time:
🔊 Formula
TIME(f(n)) ⊆ SPACE(f(n)) ⊆ TIME(2O(f(n)))
The first inclusion is trivial (can't visit more cells than steps). The second says: a machine
using f(n) space has at most exponentially many configurations, and
if it halts, it must do so before repeating one — giving a time bound.
🔊 Widget
Space vs. time on the same problem Widget 1 · Auto-plays
Reusable cells
Many algorithms can reuse the same memory cells over and over — taking polynomial time but
logarithmic space. The graph compares space usage and time usage for typical algorithms.
🎧 Narration
2 · Savitch's theorem: NSPACE ⊆ SPACE(f²)
🔊 Diagram
Savitch's recursion tree has 2^(log t) leaves — exponentially many nodes — but at any moment only a single root-to-leaf path occupies the call stack. log t × O(f) bits per frame = O(f²) space, proving NSPACE(f) ⊆ SPACE(f²).
A nondeterministic machine using f(n) space can be simulated by a
deterministic machine using only O(f(n)2) space.
The trick is recursive: to test whether configuration A can reach
B in t steps, guess a midpoint
M and recursively test "A reaches
M in t/2" AND "M
reaches B in t/2." We never need both
recursive calls active at once, so the call stack has depth log t = O(f(n)),
each frame holding configurations of size O(f(n)). Total:
O(f(n)2).
🔊 Widget
Savitch's recursion tree Widget 2 · Auto-plays
Recursion tree
Watch the tree expand. Each node is a CANYIELD(A, B, t) call. The two children are the same
with t/2. We don't store all of them — at any moment only one path is live, so the call stack
has depth log t.
🔊 Callout
Consequence
PSPACE = NPSPACE. (For polynomial f, f² is still polynomial.) This makes
nondeterminism free in the polynomial-space world.
🎧 Narration
3 · TQBF is the canonical PSPACE-complete problem
A quantified Boolean formula looks like:
🔊 Formula
∃x₁ ∀x₂ ∃x₃ … φ(x₁, x₂, …, xn)
The TRUE-QBF (TQBF) problem asks whether the formula is true. Evaluating it naturally
corresponds to a 2-player game: ∃ tries to make φ true, ∀ tries to make it false.
🔊 Widget
TQBF as a game tree Widget 3 · Auto-plays
Game
∃-nodes (green) want at least one TRUE child. ∀-nodes (orange) need every child TRUE.
Watch the tree evaluate bottom-up.
🎧 Narration
4 · Generalized Geography — play it yourself
Two players take turns moving a token along directed edges of a graph. Each vertex can be
visited at most once. The player who cannot move loses. This is Generalized Geography
— and it is PSPACE-complete.
🔊 Widget
Play Generalized Geography against the computer Widget 4 · Interactive
Click a neighbor of the current red token to move.
Turn You (Player 1)
Visited {start}
Verdict in progress
How to play
Click any node that has an arrow from the current red token. Then the computer (Player 2)
plays optimally. If you can force the computer to face no moves, you win.
🔊 Key idea
Why Geography is PSPACE-complete. Any TQBF formula can be encoded as a
geography graph where the ∃ player chooses vertices for existential variables and the ∀ player
for universals. The game forces both players to commit to a deepening play tree of total depth
polynomial in the formula.
🎧 Narration
5 · The big picture
🎧 Narration
6 · Practice (Sipser §8.1–§8.3)
Sipser 8.1
Show that {0k : k = 2j} ∈ SPACE(log n).
Show solution outline
Count input length n in binary (log n bits). Repeatedly check if it's even and divide by 2; accept if you reach 1, reject if odd > 1.
Sipser 8.4
Show that ADFA ∈ L (logarithmic space).
Show solution outline
Store only the current DFA state (log(|Q|) bits) and an index into the input (log n bits). Read one symbol, update state, repeat. Total log space.
Sipser 8.8
Show that PATH ∈ NL.
Show solution outline
Nondeterministic log-space algorithm: store current vertex (log n bits) and step count (log n bits). At each step, guess a neighbor; accept if target reached within n steps.
Sipser 8.13
Show that PSPACE is closed under union, complement, and Kleene star.
Show solution outline
Complement: flip accept/reject (deterministic machine; works directly). Union: run both deciders in turn. Star: a polynomial-space algorithm guesses splits and recurses.
Sipser 8.21
The cat and mouse game: two players move on a graph, cat caught if same vertex. Show this problem is PSPACE-complete.
Show solution outline
In PSPACE: minimax game tree of polynomial depth, recurse in polynomial space. PSPACE-hard: reduce from Generalized Geography by encoding moves as cat/mouse positions.
🎧 Narration
One-sentence summary
🔊 Key idea
PSPACE = NPSPACE (Savitch), and the "natural" games — TQBF, Generalized Geography — are
PSPACE-complete; equivalently, PSPACE is the class of decision problems whose solutions look
like perfect play in a polynomial-depth game.