P46 · Time hierarchy

🔊 Listen

1 · Time Hierarchy Theorem · more time = more languages

The Time Hierarchy Theorem (Hartmanis & Stearns 1965) is one of the few unconditional separation results in complexity theory. It says that giving a TM strictly more time strictly enlarges what it can decide.

Theorem (Sipser 9.10)

If f(n) ≥ n log n is time-constructible, then TIME(f(n)) ⊊ TIME(f(n) · log f(n)).

The proof is by diagonalisation. Build a TM D that on input ⟨M⟩ simulates M for f(|⟨M⟩|) steps and outputs the opposite of M's answer. D's language is not in TIME(f) (any TIME(f) machine M would disagree with D on input ⟨M⟩) but D runs in time f · log f (the extra log factor accounts for universal-simulation overhead).

Major consequences

P ⊊ EXPTIME. TIME(n^k) ⊊ TIME(2ⁿ) for every k. EXPTIME strictly contains polynomial time.

TIME(n) ⊊ TIME(n²). Linear time is strictly less than quadratic time.

NL ⊊ PSPACE. Via Space Hierarchy (analogous theorem for space).

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

The log factor is real but small. TIME(n) ⊊ TIME(n²) is provable via this theorem; TIME(n) vs TIME(n log² n) is also separable but tightly. Removing the log factor would be a major theorem.
The theorem doesn't apply to NP vs P. Determinism vs nondeterminism is orthogonal to the time-resource axis. P ⊊ NP could be true even though P ⊊ EXPTIME is proven.
"Time-constructible" matters. The diagonalizer needs to know when to stop. If f isn't computable in O(f) time, the proof fails.

🔊 Listen

4 · Q&A defence notes

Q1. Why log f overhead in the simulation?
A universal TM simulating a TIME(f) machine needs log f extra time per step for bookkeeping — looking up the simulated transition table, tracking the simulated head position, scaling the simulated tape. The factor log f is the cost of indirection.
Q2. Why "time-constructible"?
D must compute f(n) on its own clock to know when to halt simulation and output the opposite. Time-constructibility says f(n) can be computed in O(f(n)) time — fast enough to not blow the budget.
Q3. Does this prove P ⊊ NP?
No. P and NP differ in determinism (yes-instances need certificates vs require deterministic search). The Time Hierarchy compares time bounds within the same model. P ⊊ EXPTIME is unconditionally proven; P ⊊ NP is open.
Q4. Is there a Space Hierarchy theorem?
Yes. SPACE(f) ⊊ SPACE(f · g) for any space-constructible f and unbounded g. Tighter than the time version because space simulation has no log overhead. Gives L ⊊ PSPACE and NL ⊊ PSPACE.

🔊 Listen

5 · Where to read more

Sipser: Theorem 9.10 (Time Hierarchy). Lecture notes: Module 7 slide 5. Companion problems: P45 (hierarchy diagonal), P48 (P ⊊ EXPTIME).