A researcher claims that DTIME(n²) = DTIME(n³) — that cubic time provides no additional computational power over quadratic time. The time hierarchy theorem implies:
AThis is possible; the theorem only applies when the time bounds differ by an exponential factor
BThis is false — the theorem unconditionally guarantees DTIME(n²) ⊊ DTIME(n³), so there are languages requiring cubic time that cannot be solved in quadratic time
CThis is an open question, analogous to P vs. NP, requiring new proof techniques to resolve
DThis is false only if P ≠ NP; otherwise additional time might not help within polynomial time
The time hierarchy theorem provides an unconditional separation: given time-constructible f and g satisfying f(n)·log f(n) = o(g(n)), we have DTIME(f) ⊊ DTIME(g). For n² and n³: (n²)·log(n²) = 2n²log n = o(n³), so the condition is met and DTIME(n²) ⊊ DTIME(n³) holds without any assumptions. This is a proven theorem, not a conjecture. The claim DTIME(n²) = DTIME(n³) is simply false, as a matter of proven mathematics — no appeal to P vs. NP is needed.
Question 2 Multiple Choice
The time hierarchy theorem's proof constructs a language not in DTIME(f) by building a TM D that operates in time g(n). The key mechanism is:
AReducing DTIME(f) to the halting problem and showing the halting problem is not in DTIME(g)
BShowing that the complement of any language in DTIME(f) lies in DTIME(g) by a padding argument
CDiagonalizing: D simulates each time-f TM Mᵢ on input ⟨i⟩ and does the opposite, ensuring D's language differs from every time-f machine on at least one input
DUsing a counting argument to show DTIME(g) must contain more languages than DTIME(f)
Diagonalization is Cantor's trick applied to computability. The TM D has budget g(n). On input ⟨i⟩, it simulates Mᵢ on ⟨i⟩ for f(|⟨i⟩|)·log f(|⟨i⟩|) steps — affordable because g grows faster. If Mᵢ accepts, D rejects; if Mᵢ doesn't accept in time, D accepts. By construction, D's language differs from every time-f machine on the input ⟨i⟩ corresponding to that machine. So D's language is not in DTIME(f), but D itself runs in time g(n), placing the language in DTIME(g). The log f overhead accounts for the simulation slowdown.
Question 3 True / False
The time hierarchy theorem proves P ⊊ EXPTIME unconditionally — no unproven conjectures are required.
TTrue
FFalse
Answer: True
P = DTIME(n^k for all k), and EXPTIME = DTIME(2^{n^k} for all k). Taking f = n^k and g = 2^n, we have f(n)·log f(n) = n^k · k·log n = o(2^n), so the hierarchy theorem applies and gives DTIME(n^k) ⊊ DTIME(2^n). Since this holds for every polynomial k, P ⊊ EXPTIME is proven as a theorem. This is one of the few unconditional separations in complexity theory — most other separations (like P vs. NP or P vs. PSPACE) remain open conjectures.
Question 4 True / False
Because the time hierarchy theorem proves separations between deterministic time classes using diagonalization, the same technique can be applied to prove P ≠ NP.
TTrue
FFalse
Answer: False
The diagonalization argument works cleanly for DTIME(f) vs. DTIME(g) because both sides are deterministic: D can simulate any deterministic TM Mᵢ in a predictable way. The argument breaks down for deterministic vs. nondeterministic comparisons (P vs. NP) because nondeterministic TMs can produce exponentially many computation paths — a deterministic simulator cannot enumerate and 'do the opposite of' all of them within a polynomial time budget. This barrier is formalized by the relativization result: there exist oracles relative to which P=NP and oracles relative to which P≠NP, meaning diagonalization-based proofs cannot resolve P vs. NP.
Question 5 Short Answer
Explain why the time hierarchy theorem is an unconditional result, and contrast this with the open status of P vs. NP.
Think about your answer, then reveal below.
Model answer: The time hierarchy theorem is unconditional because its proof — diagonalization over deterministic TMs — is entirely constructive and makes no unverified assumptions. We explicitly build a TM D that runs in time g(n) and decides a language provably not in DTIME(f(n)). Every step of the argument is verified mathematics. P vs. NP asks whether nondeterministic polynomial time adds power over deterministic polynomial time. Here the diagonalization technique fails: a deterministic simulator of an NTM may not fit within polynomial time, and no other proof technique has succeeded. The separation might be true (P≠NP) or false (P=NP), but proving either direction requires fundamentally new ideas that bypass the known barriers to diagonalization-style proofs.
The contrast highlights why unconditional separations are rare in complexity theory. Within deterministic time, we have a clean simulation relationship: a DTM can simulate another DTM with a known overhead, making diagonalization work. The moment nondeterminism enters, or we ask about space vs. time, the simulation relationships become unclear and diagonalization fails to give a clean separation. This is the heart of why P vs. NP is hard — not that the answer is unknown, but that our current proof tools are provably insufficient to decide it.