The time hierarchy theorem guarantees that DTIME(n²) ⊊ DTIME(n³). What proof technique establishes this separation, and why does it work?
ACircuit complexity lower bounds — circuits for problems in DTIME(n³) require more gates than DTIME(n²) circuits
BDiagonalization — construct a machine that uses n³ time and does the opposite of every n²-time machine on some input, ensuring no n²-time machine can simulate it
CPadding arguments — pad inputs to create a problem solvable in n³ time that cannot be solved in n² time
DReduction from NP-complete problems — since NP ⊄ P, higher time classes must be strictly larger
Diagonalization is the proof technique. Construct machine D that, given input x of length n, simulates n³ steps of the machine M_x (using x as a description of a machine) and outputs the opposite of whatever M_x would output. If any n²-time machine M could decide the same language as D, we get a contradiction when we give M its own description: M cannot simulate D on that input in n² time because D uses n³ time to do the opposite of M. The n log n condition in the full theorem (f(n) log f(n) < g(n)) accounts for the overhead of the universal simulation. Diagonalization is self-referential — it exploits the fact that Turing machines can simulate each other.
Question 2 Multiple Choice
The time hierarchy theorem proves P ⊊ EXPTIME. What does this NOT tell us about the P vs. NP question?
AIt tells us nothing about P vs. NP because the hierarchy theorem only separates deterministic time classes from each other
BIt implies P ≠ NP because NP lies strictly between P and EXPTIME
CIt proves NP ≠ EXPTIME, which combined with NP ⊆ EXPTIME gives a useful constraint on NP
DIt shows that NP-complete problems are not in P, since any problem requiring exponential time cannot be in P
The time hierarchy theorem separates DTIME classes — classes defined by deterministic computation. P ⊊ EXPTIME means there are problems solvable in exponential deterministic time but not polynomial deterministic time. NP is defined by nondeterministic computation, which the hierarchy theorem says nothing about. We cannot conclude P ≠ NP because NP might equal P (still unknown) or NP might be strictly between P and EXPTIME — the hierarchy theorem doesn't constrain where NP sits relative to P. Option B is the classic mistake: NP being 'between' P and EXPTIME does not entail P ≠ NP. The separation is between deterministic classes; NP's relationship to P remains the central open problem in complexity theory.
Question 3 True / False
The space hierarchy theorem has a simpler condition than the time hierarchy theorem — f(n) = o(g(n)) suffices, without the log factor — because space can be reused across computation steps.
TTrue
FFalse
Answer: True
In time complexity, simulating a machine on a universal Turing machine incurs an O(log f(n)) overhead per step, leading to the f(n) log f(n) condition. For space, the universal simulation overhead is constant per cell used — and crucially, space can be reused: cells used in one part of the computation can be cleared and reused later. This makes space simulation cheaper, and the simple f(n) = o(g(n)) condition suffices to ensure the simulated machine stays within the resource budget. The reusability of space is a fundamental asymmetry between time and space complexity that appears repeatedly in complexity theory (e.g., PSPACE contains NP, but time classes don't have such simple nesting).
Question 4 True / False
The hierarchy theorems prove that the complexity landscape is infinite — no single complexity class contains most computable problems — and also prove that P ≠ NP.
TTrue
FFalse
Answer: False
The hierarchy theorems prove the first claim but not the second. They show DTIME(f(n)) ⊊ DTIME(g(n)) whenever g grows sufficiently faster than f, establishing infinitely many distinct deterministic time complexity classes. But P ≠ NP is a separation between deterministic and nondeterministic computation — a fundamentally different type of separation. The hierarchy theorems use diagonalization over deterministic machines and cannot capture the distinction between deterministic and nondeterministic power. P vs. NP remains open precisely because no known technique (including diagonalization) can prove lower bounds for specific problems against all polynomial-time algorithms.
Question 5 Short Answer
Why is diagonalization sufficient to prove the time hierarchy theorem, but not sufficient to separate P from NP?
Think about your answer, then reveal below.
Model answer: Diagonalization works for the hierarchy theorem because it separates two classes defined by the same computational model (deterministic Turing machines) with different resource bounds. The diagonalizing machine D can simulate any f(n)-time machine and do the opposite — this is self-referential but well-defined. For P vs. NP, diagonalization would need to separate deterministic from nondeterministic computation. But any diagonalization argument against P must work against ALL polynomial-time machines simultaneously, including those that might simulate nondeterminism in clever ways. The 'relativization barrier' (Baker-Gill-Solovay) formalizes this: there exist oracles relative to which P = NP and others where P ≠ NP, so any proof technique that 'relativizes' (including diagonalization) cannot resolve P vs. NP.
The key insight is that hierarchy theorem diagonalization exploits a gap in resource bounds within the same model. P vs. NP requires reasoning about the *structural* power of nondeterminism versus determinism — a question about what it means to 'guess' versus 'search.' No elegant self-referential construction like diagonalization has succeeded, because the argument must somehow encode the difficulty of specific combinatorial problems (like satisfiability), not just resource bookkeeping. This is why complexity theorists believe P ≠ NP but cannot prove it.