The space hierarchy theorem · via diagonalization

The hierarchy theorems are the only unconditional separation results in complexity theory. Every famous open problem — P vs NP, P vs PSPACE, NL vs L — asks whether two classes are equal. We don't know. But we do know, for sure, that strictly more space (or time) gives strictly more power, as long as the gap is big enough.

These are the theorems that anchor the complexity zoo. Without them, the picture L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME would have no proven inequalities at all. The hierarchy theorems guarantee at least one strict containment in every "long enough" stretch of the chain.

The recipe is Cantor's, with three new ingredients:

1. Enumerate the machines we want to defeat: M₁, M₂, … = all TMs using ≤ f(n) space. (We can list TM descriptions lexicographically.)
2. Build D = "on input ⟨M⟩: simulate M(⟨M⟩) using a counter to enforce f(n) space; if M halts with answer b, output 1-b."
3. Argue D's resources: D uses f(n) for the simulated tape, plus O(log f(n)) for a counter, total O(f(n) · log f(n)).

Claim 1. D ∉ SPACE(f). Suppose, for contradiction, D ∈ SPACE(f). Then D = M_k for some k. Run D on input ⟨M_k⟩ = ⟨D⟩:

• By the table, M_k(⟨M_k⟩) = some bit b.
• By D's construction, D(⟨M_k⟩) = 1 − b.
• But D = M_k. So b = 1 − b. Contradiction.

Claim 2. D ∈ SPACE(f · log f). The simulation uses f(n) tape cells for M's tape and O(log f(n)) for head/state/counter. Total: O(f · log f). ∎

The animation walks the diagonal: row by row, watch the cell where M_i meets ⟨M_i⟩, then watch D's row appear in gold flipping every diagonal answer.

Apply the theorem with f(n) = log n (i.e. L):

• SPACE(log n) = L ⊊ SPACE(log n · log log n) ⊆ SPACE(log² n).
• Keep iterating: SPACE(log² n) ⊊ SPACE(log² · log log²) ⊆ SPACE(log³).
• Eventually we cross into SPACE(n) and beyond. SPACE(n) ⊊ SPACE(n²) ⊊ … ⊊ SPACE(n^k) for any growing k.

So L is strictly inside PSPACE = ∪_k SPACE(n^k). Each strict step is small (log factor), but a chain of strict steps eventually crosses any polynomial gap.

• Time hierarchy theorem · TIME(t) ⊊ TIME(t · log t). Same diagonal idea, time-clocked simulation. P ⊊ EXPTIME via this.
• Nondeterministic hierarchy · NTIME(t) ⊊ NTIME(t · log t) (Cook 1972, Seiferas–Fischer–Meyer 1978). NP ⊊ NEXPTIME.
• Gap theorem · Borodin/Constable: there exist computable f such that TIME(f) = TIME(2^f). The hierarchy is not entirely smooth.
• Speedup theorem · Blum: for some L, every TM solving L has a faster TM solving L. Resource bounds aren't always achievable optimally.
• Open: P ⊊ PSPACE · believed true but unproven. The hierarchy theorems give P ⊊ EXPSPACE but cannot squeeze between P and PSPACE.

1. "Hierarchy proves P ≠ NP." No. P and NP are not separated by hierarchy: both are bounded by polynomial resources. The diagonal needs a resource gap.
2. Ignoring constructibility. Without f being space-constructible, D doesn't know when to stop simulating. The theorem genuinely needs the hypothesis.
3. Confusing the log f gap with log n. The simulation overhead depends on f, not n directly. For f = n, the gap is log n. For f = log n, the gap is log log n.
4. "D's contradiction is M_k(⟨M_k⟩) = M_k(⟨M_k⟩) + 1." Almost — it's b = 1−b, which means 2b = 1, impossible for a bit.
5. "This needs Cantor's bijection." No, just a TM enumeration. We never need to enumerate all reals.

• Q1. Why "space-constructible"?
  D needs to compute f(n) on its own work-tape to know when to stop simulating. f(n) being space-constructible means there's a TM that on input 1ⁿ computes f(n) using O(f(n)) space. Every standard function (n, n², 2ⁿ, …) qualifies.
• Q2. Why exactly the f · log f gap, not f?
  D must simulate any SPACE(f) machine. A space-f simulation needs a small log f overhead to track the simulated machine's tape head, state, and clock. That's where the log factor comes from.
• Q3. Why doesn't this prove P ⊊ NP?
  The hierarchy theorem only separates classes that differ in their resource bound. P and NP both use polynomial resources — they differ in determinism, not in resource amount. The diagonal trick doesn't directly compare deterministic vs nondeterministic.
• Q4. Can you state the time hierarchy theorem and the analogous proof?
  If t(n) ≥ n log n is time-constructible, then TIME(t(n)) ⊊ TIME(t(n) · log t(n)). Proof: build a time-diagonalizer that simulates each TIME(t) machine on its own description, with a clock that times out after t(n)·log t(n) steps. The log overhead is for the simulation bookkeeping.
• Q5. What known separation comes out of this?
  NL ⊆ SPACE(log²) (Savitch) ⊆ SPACE(log² · log log²) ⊊ SPACE(log³) ⊆ … ⊊ SPACE(n^k) = PSPACE. So NL ⊊ PSPACE strictly. Similarly P ⊊ EXPTIME by time hierarchy.

Total time: 12 minutes.

• (1 min) Hook: "Among all the unproven separations (P vs NP, L vs NL, …), is there any separation we can actually prove?"
• (2 min) State the theorem. Emphasize "f · log f" — small but non-trivial gap.
• (3 min) Construct D on the board. Three lines: enumerate, simulate, flip.
• (3 min) Run the visualization. Pause when D's row appears in gold. Walk through the "b = 1 − b" contradiction.
• (2 min) List the corollaries: L ⊊ PSPACE, NL ⊊ PSPACE, P ⊊ EXPTIME, NP ⊊ NEXPTIME.
• (1 min) Close with the limit: hierarchy cannot give P ≠ NP — different determinism, same resource bound.