Theory of Computational Complexity, 2nd Edition

For the time-bounded classes, we show a weaker result.

Theorem 1.23

(Time Hierarchy Theorem) If t₂ is a fully time-constructible function, and

then .

Proof

The proof is similar to the space hierarchy theorem. The only thing that needs extra attention is that the machines M_x may have an arbitrarily large number of tapes over an arbitrarily large alphabet, while the new machine M^∗ has only a fixed number of tapes and a fixed-size alphabet. Thus, the simulation of M_x on x by M^∗ may require extra time. This problem is resolved by considering the enumeration of two-worktape TMs over a fixed alphabet and relaxing the time bound to (Theorem 1.15).

A nondecreasing function f(n) is called superpolynomial if

for all i ≥ 1. For instance, the exponential function 2ⁿ is superpolynomial, ...