Space Complexity and Savitch's Theorem
Stub. Measuring memory rather than time: Savitch's theorem (nondeterministic space is only quadratically more powerful than deterministic space — in sharp contrast to the time case, where P vs. NP is wide open), the class PSPACE and PSPACE-completeness (the TQBF problem, winning strategies for games, generalized geography), and the smaller classes L and NL, NL-completeness, and the surprising NL = coNL theorem.
Corresponds to Sipser, Chapter 8, and overlaps with the advanced course’s Lecture 2, Part 1 (space-bounded computation, Savitch’s theorem, L vs. NL). Space complexity has a structural advantage time complexity lacks: Savitch’s theorem shows any nondeterministic space- computation can be simulated deterministically in only space — so, unlike P vs. NP, the deterministic/nondeterministic space classes are provably close. PSPACE (polynomial space) turns out to contain surprisingly expressive, game-like complete problems (TQBF — true quantified Boolean formulas — captures the structure of an alternating game tree, as does deciding the winner of generalized geography). At the low end, L (logarithmic space) and NL are small enough to be practically relevant (e.g. for graph reachability, NL-complete via searching in graphs), and the chapter’s capstone, NL = coNL, is a genuinely surprising closure result (complementing an NL language doesn’t need more space) that doesn’t have a time-complexity analogue. This basic space-bounded toolkit (and in particular undirected graph connectivity, the canonical NL-complete problem) is exactly the starting point the advanced course’s expander-graph material builds toward (SL = L).
Outline (TODO — flesh out each)
- Savitch’s theorem
- The class PSPACE
- PSPACE-completeness — TQBF, winning strategies for games, generalized geography
- The classes L and NL
- NL-completeness — searching in graphs
- NL equals coNL