1 · NL ⊊ PSPACE · strict containment via Savitch + hierarchy
One of the few unconditional strict separations between named complexity classes: NL is properly contained in PSPACE. The proof chains two theorems.
Savitch's theorem
NL = NSPACE(log n) ⊆ SPACE(log² n). (Problem 35.) This puts NL inside polynomial space.
Space Hierarchy theorem
For space-constructible f and unbounded g: SPACE(f) ⊊ SPACE(f · g). So SPACE(log² n) ⊊ SPACE(log² n · log log n) ⊊ … ⊊ SPACE(n) ⊊ SPACE(n²) ⊊ … ⊊ PSPACE.
Combining: NL ⊆ SPACE(log² n) ⊊ PSPACE. So NL ⊊ PSPACE strictly.
Where the gap sits
The exact extent of NL inside PSPACE is unknown. We know NL ⊊ PSPACE; we conjecture NL ⊊ P ⊊ PSPACE. But P-NL and P-PSPACE could both be equal — neither is ruled out without further separation results.
2 · Animated demo · auto-plays · loops
3 · Pitfalls
- Hierarchy theorems separate same-resource classes. SPACE(f) ⊊ SPACE(f · log) — same resource, more of it. Hierarchy doesn't compare time vs space, or det vs nondet.
- NL ⊊ PSPACE is the cleanest separation we have around the polynomial-space scale. NL ⊊ P, P ⊊ NP, NL ⊊ P ⊊ NP ⊊ PSPACE — all but NL ⊊ PSPACE are open.
- The quadratic gap matters. Savitch's log²n bound is the tightest known for general NSPACE → SPACE conversion. Tightening this is a major open problem.
4 · Q&A defence notes
Q1. Why Savitch?
NL = NSPACE(log n) ⊆ SPACE(log² n) by Savitch. This is what gets nondeterministic log space inside deterministic poly space. Without Savitch, we'd have no easy comparison between NSPACE(log n) and any DSPACE class.
Q2. Why is the chain "strict everywhere"?
Each inclusion in SPACE(log² n) ⊊ SPACE(log² n · log) ⊊ … is by the Space Hierarchy Theorem. Each step uses the same diagonalisation technique to find a language one level can't decide but the next level can.
Q3. Why don't we know NL ⊊ P or P ⊊ NP?
Those comparisons span different resource types — nondeterministic space vs deterministic time, or deterministic time vs nondeterministic time. Hierarchy theorems only separate same-resource bounds. Cross-resource separations require new techniques.
Q4. What's known about NL vs P?
NL ⊆ P (trivially). Whether NL ⊊ P is open. Many believe yes; no proof exists.
5 · Where to read more
Sipser: Theorem 9.10 (Time Hierarchy), §9.1 (Space Hierarchy), Theorem 8.5 (Savitch). Lecture notes: Module 7 slide 5. Companion problems: P35 (PSPACE = NPSPACE), P46 (time hierarchy).