The smallest natural complexity classes — and the one separation theorem we can actually prove.
BCS 402 · Dr. Arash Kermani · CUD
🎧 Narration
🔊 Diagram
The full nested-ovals map of complexity classes. Strict containments between adjacent classes are mostly open (P vs NP, NP vs PSPACE, PSPACE vs EXPTIME) — but the hierarchy theorems give us at least L ⊊ PSPACE, P ⊊ EXPTIME, and PSPACE ⊊ EXPSPACE.
1 · L and NL — counting with logarithmic memory
For tiny space, we use a 2-tape model: a read-only input tape (doesn't count
toward space) and a work tape (does). A language is in L if some deterministic
machine decides it using O(log n) work-tape cells. NL
is the nondeterministic version.
🔊 Formula
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE
Log space is barely enough to store a pointer into the input. That's the right metaphor:
L is the class of problems solvable by reading the input while maintaining only a
constant number of pointers into it.
🔊 Widget
A log-space machine in action Widget 1 · Auto-plays
Work tape ∅
Work cells used 0
Verdict —
🎧 Narration
2 · PATH is NL-complete
PATH: given a directed graph and two vertices s and
t, is there a directed path from s to
t? PATH is the canonical NL-complete problem. The proof uses
log-space reductions.
PATH is in NL by the following nondeterministic algorithm: store the current vertex (
log n bits) and a step counter (
log n bits). At each step, guess a neighbor; if it's the target
within n steps, accept.
🔊 Widget
Nondeterministic guesses on PATH Widget 2 · Auto-plays
Configurations explored 0
Space used log n + log n bits
Branching
Watch the nondeterministic computation explore all paths in parallel. Each branch only needs
log n bits to track current vertex + step counter.
Why is PATH NL-hard? Given any NL machine M and input
w, construct the configuration graph: vertices are configurations of
M on w, edges are δ-transitions. There are
2O(log n) = poly(n) configurations — the graph is
polynomial in size, constructible in log space. Then M accepts iff
there is a path from start config to accept config in this graph.
🎧 Narration
3 · Immerman–Szelepcsényi: NL = coNL
Astonishingly, NL is closed under complement: NL = coNL. The proof
technique is inductive counting.
To show PATH is in NL, we need an NL algorithm that
accepts iff there is NO path from s to t.
The idea: count the number of vertices reachable from s in
≤ i steps (call this ci), and use
ci to certifyci+1. If we
arrive at cn and the target t is NOT in
that count, then there is no path.
🔊 Widget
Inductive counting on the configuration graph Widget 3 · Auto-plays
Step i 0
ci (vertices reachable in ≤ i steps) 1
🔊 Callout
What inductive counting buys us
Once we know cn, we can in NL "for each vertex, certify it is
reachable or unreachable using cn as a witness count." Then
checking t ∉ R is a positive existential check, doable in NL.
So PATH ∈ NL, and since PATH is NL-complete, every NL
language is closed under complement. ∎
🎧 Narration
4 · The hierarchy theorems
🔊 Diagram
The space hierarchy theorem is proved by diagonalization. We enumerate all SPACE(f) machines, then build D that disagrees with each on its own description. D uses slightly more space (a log factor) — exactly the gap between SPACE(f) and SPACE(f log f).
More space = more languages decidable. The space hierarchy theorem:
🔊 Formula
if f(n) is space-constructible and f(n) ≥ log n, then SPACE(f(n)) ⊊ SPACE(o(f(n) · log f(n))).
A similar theorem holds for time. The proofs are by diagonalization — just
like the proof that ATM is undecidable, but now with resource bounds.
Each row is a TM with space ≤ f(n). The diagonalizer D runs Mi on ⟨Mi⟩ in space slightly
larger than f, and flips the answer. D cannot be in SPACE(f) — so SPACE(g) strictly
contains SPACE(f).
🔊 Key idea
Concretely known separations.
NL ⊊ PSPACE (consequence of space hierarchy).
P ⊊ EXPTIME.
NP ⊊ NEXPTIME.
Whether P ⊊ NP is open — but at least we know some
separations exist, thanks to the hierarchy theorems.
🎧 Narration
5 · The full map (everything we've covered)
🎧 Narration
6 · Practice (Sipser §8.4–§9.1)
Sipser 8.22
Show that EQDFA ∈ NL.
Show solution outline
Equivalent to: ⟨D₁, D₂⟩ accept iff for no string w does D₁ accept w ≠ D₂ accept w. Use NL = coNL: nondeterministically guess a string causing disagreement (track current state in each DFA, log space).
Sipser 8.23
Show that 2SAT ∈ NL.
Show solution outline
Use the implication graph: from each clause (x ∨ y) derive ¬x → y and ¬y → x. φ is UNSAT iff some variable z has both z → ¬z and ¬z → z paths. Using NL for PATH, the complement (SAT) is in NL by NL = coNL.
Sipser 9.1
Show that there is a function f : ℕ → ℕ such that f(n) = Ω(log n) and TIME(f(n)) ⊊ TIME(f(n) log f(n)).
Show solution outline
Direct application of the time hierarchy theorem. Pick f(n) = n · log n, which is time-constructible; the theorem gives TIME(f) ⊊ TIME(f log f) = TIME(n log² n · log log n).
Sipser 9.3
Show that for any function f : ℕ → ℕ with f(n) ≥ n, the class NSPACE(f(n)) is closed under complementation.
Show solution outline
Immerman–Szelepcsényi: the proof for NL generalizes — same inductive counting works whenever you can count the configurations in your space bound. For f(n) ≥ n, configurations are at most 2^O(f(n)), and counting them takes O(f) space.
Sipser 9.10
Recall that EXPTIME = ⋃k TIME(2nk). Show that P ⊊ EXPTIME.
Show solution outline
Direct from the time hierarchy theorem: TIME(n^k) ⊊ TIME(2ⁿ) for any constant k. So P ⊊ TIME(2ⁿ) ⊆ EXPTIME.
🎧 Narration
One-sentence summary of the whole course
🔊 Key idea
Algorithms are bounded by what's computable (diagonalization rules out the undecidable) and by
resources (time and space hierarchy theorems separate classes within the decidable); the few
proven separations and the many open ones (P vs NP being the headline) define the landscape of
modern complexity theory.