A complexity theorist claims: 'We believe DTIME(n) is strictly contained in DTIME(n²), but we cannot prove it — just like the P vs NP problem.' Is this statement correct?
AYes — separations between polynomial time classes are all equally unproven conjectures, just like P ≠ NP
BNo — DTIME(n) ⊊ DTIME(n²) is provable using the time hierarchy theorem, unlike P ≠ NP
CNo — we can actually prove DTIME(n) = DTIME(n²) because linear-time algorithms can always be optimized to match quadratic ones
DYes — the diagonalization technique is used in both, but neither proof has been completed
The time hierarchy theorem gives a provable, unconditional separation: DTIME(n) ⊊ DTIME(n log n · log(n log n)), and since n² grows much faster than n log²n, DTIME(n) is strictly contained in DTIME(n²). This is proven — not conjectured. This is what makes the theorem remarkable: most complexity separations (P ≠ NP, NP ≠ PSPACE) remain unproven despite decades of effort. The time hierarchy theorem uses a diagonalization argument that works precisely because the time bounds differ by a superlogarithmic factor, giving the diagonal machine room to operate without being simulatable within the smaller bound.
Question 2 Multiple Choice
The time hierarchy theorem states that DTIME(f(n)) ⊊ DTIME(g(n)) when g(n) grows faster than f(n) log f(n). Why is a log factor required — why isn't a strict improvement g(n) > f(n) sufficient?
AThe log factor accounts for the polynomial overhead of multi-tape Turing machines compared to single-tape models
BThe log factor is the per-step overhead paid by a universal Turing machine to simulate another Turing machine — the diagonal machine must absorb this cost while still fitting within the larger time bound
CThe log factor ensures the bounding functions are time-constructible, which is required for the proof
DThe log factor represents the number of tape heads needed by the diagonal machine to track the simulated machine's state
A universal Turing machine simulating machine M_x on input x incurs a logarithmic overhead per simulated step — it must track M_x's state, head position, and tape contents, requiring O(log n) bookkeeping per step. So the diagonal machine D, which simulates M_x for f(n) steps, runs in O(f(n) log f(n)) total steps. If g(n) only slightly exceeded f(n) — without this log gap — the simulation overhead might fill the gap, and D might actually be computable within f(n) steps, collapsing the separation. The log factor is precisely the space that keeps D's runtime in DTIME(f(n) log f(n)) but out of DTIME(f(n)).
Question 3 True / False
The time hierarchy theorem establishes that P is strictly contained in EXP — a provable, unconditional result that does not depend on any unproven conjecture.
TTrue
FFalse
Answer: True
By the time hierarchy theorem, for any polynomial p(n), DTIME(p(n)) ⊊ DTIME(2^{p(n)}) because 2^{p(n)} grows much faster than p(n) log p(n). Therefore P = ∪_k DTIME(n^k) is strictly contained in EXP = ∪_k DTIME(2^{n^k}). This is one of the few proven, absolute separations in complexity theory — no unproven conjectures needed. It confirms that the complexity hierarchy has genuine structure: exponential-time computation is provably more powerful than polynomial-time computation, even though we cannot yet determine where specific boundaries like P vs NP fall.
Question 4 True / False
The diagonalization argument in the time hierarchy theorem works by finding a specific language that is in DTIME(f(n)) and also in DTIME(f(n) log f(n)), thereby establishing a separation.
TTrue
FFalse
Answer: False
The diagonal argument constructs a language that is in DTIME(f(n) log f(n)) but provably NOT in DTIME(f(n)). The diagonal machine D, on input x, simulates the f(n)-bounded machine M_x on x using a universal TM, then does the opposite of whatever M_x does. This guarantees D's language differs from every f(n)-bounded language on at least one input — so no f(n)-bounded machine can compute D's language. The whole point is separation (establishing a language outside the smaller class), not inclusion. A language that is in both classes would prove equality, not strict containment.
Question 5 Short Answer
Explain why the diagonal machine in the time hierarchy theorem proof must 'do the opposite' of the machine it simulates, and why this guarantees the diagonal language is not in DTIME(f(n)).
Think about your answer, then reveal below.
Model answer: The diagonal machine D works as follows: on input x, interpret x as a machine description M_x, simulate M_x on x for f(|x|) steps using a universal TM, then accept if M_x rejects (or times out) and reject if M_x accepts. This 'opposite' step ensures that D's language L differs from the language of every f(n)-bounded machine: for each machine M_x, the string x witnesses a disagreement — x is in L iff x is NOT accepted by M_x. Therefore no f(n)-bounded machine can decide L, because for any candidate machine M_x, we can exhibit x where M_x and D disagree. This is the Cantor diagonal argument applied to computation: just as Cantor's diagonal sequence differs from every sequence in a list, D's language differs from every f(n)-bounded language.
The 'opposite' step is the essential move — without it, D might compute the same language as some M_x and establish nothing. The flip guarantees a provable disagreement with every possible f(n)-bounded machine simultaneously. D itself runs in O(f(n) log f(n)) due to the simulation overhead, so the language it decides lives in DTIME(f(n) log f(n)) but not in DTIME(f(n)) — a strict separation.