Global InformationTime hierarchy theorem information
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 n2 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),
- ,
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 if and only if , 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
- .
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]
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Žá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.
- ^ 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.