Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n² time but not n time, where n is the input length.

The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965.^[1] It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the universal Turing machine.^[2] Consequent to the theorem, for every deterministic time-bounded complexity class, there is a strictly larger time-bounded complexity class, and so the time-bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time-constructible functions f(n),

${\displaystyle {\mathsf {DTIME}}\left(o\left(f(n)\right)\right)\subsetneq {\mathsf {DTIME}}(f(n){\log f(n)})}$,

where DTIME(f(n)) denotes the complexity class of decision problems solvable in time O(f(n)). The left-hand class involves little o notation, referring to the set of decision problems solvable in asymptotically less than f(n) time.

In particular, this shows that ${\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}$ if and only if ${\displaystyle a<b}$, so we have an infinite time hierarchy.

The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972.^[3] It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978.^[4] Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today.^[5] The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time-constructible function, and f(n+1) = o(g(n)), then

${\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))}$.

The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of advice.^[6]

Background

Both theorems use the notion of a time-constructible function. A function ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ is time-constructible if there exists a deterministic Turing machine such that for every ${\displaystyle n\in \mathbb {N} }$, if the machine is started with an input of n ones, it will halt after precisely f(n) steps. All polynomials with non-negative integer coefficients are time-constructible, as are exponential functions such as 2ⁿ.

Proof overview

We need to prove that some time class TIME(g(n)) is strictly larger than some time class TIME(f(n)). We do this by constructing a machine which cannot be in TIME(f(n)), by diagonalization. We then show that the machine is in TIME(g(n)), using a simulator machine.

Deterministic time hierarchy theorem

Statement

Time Hierarchy Theorem. If f(n) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time o(f(n)) but can be solved in worst-case deterministic time O(f(n)log f(n)). Thus

${\displaystyle {\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).}$

Equivalently, if ${\displaystyle f,g}$ are time-constructable, and ${\displaystyle f(n)\ln f(n)=o(g(n))}$, then

$${\displaystyle {\mathsf {DTIME}}(f(n))\subsetneq {\mathsf {DTIME}}(g(n))}$$

Note 1. f(n) is at least n, since smaller functions are never time-constructible.

Non-deterministic time hierarchy theorem

If g(n) is a time-constructible function, and f(n+1) = o(g(n)), then there exists a decision problem which cannot be solved in non-deterministic time f(n) but can be solved in non-deterministic time g(n). In other words, the complexity class NTIME(f(n)) is a strict subset of NTIME(g(n)).

Consequences

The time hierarchy theorems guarantee that the deterministic and non-deterministic versions of the exponential hierarchy are genuine hierarchies: in other words P ⊊ EXPTIME ⊊ 2-EXP ⊊ ... and NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊ ....

For example, ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}$ since ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}}$. Indeed, ${\displaystyle {\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\mathsf {DTIME}}\left(o\left({\frac {2^{2n}}{2n}}\right)\right)\subsetneq {\mathsf {DTIME}}(2^{2n})}$ from the time hierarchy theorem.

The theorem also guarantees that there are problems in P requiring arbitrarily large exponents to solve; in other words, P does not collapse to DTIME(n^k) for any fixed k. For example, there are problems solvable in n⁵⁰⁰⁰ time but not n⁴⁹⁹⁹ time. This is one argument against Cobham's thesis, the convention that P is a practical class of algorithms. If such a collapse did occur, we could deduce that P ≠ PSPACE, since it is a well-known theorem that DTIME(f(n)) is strictly contained in DSPACE(f(n)).

However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of computational complexity theory: whether P and NP, NP and PSPACE, PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.

Sharper hierarchy theorems

The gap of approximately ${\displaystyle \log f(n)}$ between the lower and upper time bound in the hierarchy theorem can be traced to the efficiency of the device used in the proof, namely a universal program that maintains a step-count. This can be done more efficiently on certain computational models. The sharpest results, presented below, have been proved for:

• The unit-cost random-access machine^[7]
• A programming language model whose programs operate on a binary tree that is always accessed via its root. This model, introduced by Neil D. Jones^[8] is stronger than a deterministic Turing machine but weaker than a random-access machine.

For these models, the theorem has the following form:

If f(n) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time f(n) but can be solved in worst-case time af(n) for some constant a (dependent on f).

Thus, a constant-factor increase in the time bound allows for solving more problems, in contrast with the situation for Turing machines (see Linear speedup theorem). Moreover, Ben-Amram proved^[9] that, in the above models, for f of polynomial growth rate (but more than linear), it is the case that for all ${\displaystyle \varepsilon >0}$, there exists a decision problem which cannot be solved in worst-case deterministic time f(n) but can be solved in worst-case time ${\displaystyle (1+\varepsilon )f(n)}$.

See also

• Space hierarchy theorem

References

1. Hartmanis, J.; Stearns, R. E. (1 May 1965). "On the computational complexity of algorithms". Transactions of the American Mathematical Society. 117. American Mathematical Society: 285–306. doi:10.2307/1994208. ISSN 0002-9947. JSTOR 1994208. MR 0170805.
2. Hennie, F. C.; Stearns, R. E. (October 1966). "Two-Tape Simulation of Multitape Turing Machines". J. ACM. 13 (4). New York, NY, USA: ACM: 533–546. doi:10.1145/321356.321362. ISSN 0004-5411. S2CID 2347143.
3. Cook, Stephen A. (1972). "A hierarchy for nondeterministic time complexity". Proceedings of the fourth annual ACM symposium on Theory of computing. STOC '72. Denver, Colorado, United States: ACM. pp. 187–192. doi:10.1145/800152.804913.
4. Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (January 1978). "Separating Nondeterministic Time Complexity Classes". J. ACM. 25 (1). New York, NY, USA: ACM: 146–167. doi:10.1145/322047.322061. ISSN 0004-5411. S2CID 13561149.
5. Žák, Stanislav (October 1983). "A Turing machine time hierarchy". Theoretical Computer Science. 26 (3). Elsevier Science B.V.: 327–333. doi:10.1016/0304-3975(83)90015-4.
6. Fortnow, L.; Santhanam, R. (2004). "Hierarchy Theorems for Probabilistic Polynomial Time". 45th Annual IEEE Symposium on Foundations of Computer Science. p. 316. doi:10.1109/FOCS.2004.33. ISBN 0-7695-2228-9. S2CID 5555450.
7. Sudborough, Ivan H.; Zalcberg, A. (1976). "On Families of Languages Defined by Time-Bounded Random Access Machines". SIAM Journal on Computing. 5 (2): 217–230. doi:10.1137/0205018.
8. Jones, Neil D. (1993). "Constant factors do matter". 25th Symposium on the Theory of Computing: 602–611. doi:10.1145/167088.167244. S2CID 7527905.
9. Ben-Amram, Amir M. (2003). "Tighter constant-factor time hierarchies". Information Processing Letters. 87 (1): 39–44. doi:10.1016/S0020-0190(03)00253-9.

Further reading

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Pages 310–313 of section 9.1: Hierarchy theorems.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Section 7.2: The Hierarchy Theorem, pp. 143–146.