Editing Time hierarchy theorem (section)

{{short description|Given more time, a Turing machine can solve more problems}}
In [[computational complexity theory]], the '''time hierarchy theorems''' are important statements about time-bounded computation on [[Turing machine]]s. 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''<sup>2</sup> time but not ''n'' time, where ''n'' is the input length.

The time hierarchy theorem for [[Turing machine|deterministic multi-tape Turing machines]] was first proven by [[Richard E. Stearns]] and [[Juris Hartmanis]] in 1965.<ref>{{Cite journal
 | last1 = Hartmanis | first1 = J. | author1-link = Juris Hartmanis
 | last2 = Stearns | first2 = R. E. | author2-link = Richard E. Stearns
 | doi = 10.2307/1994208
 | journal = [[Transactions of the American Mathematical Society]]
 | pages = 285–306
 | title = On the computational complexity of algorithms
 | volume = 117
 | date = 1 May 1965
 | issn = 0002-9947
 | publisher = American Mathematical Society
 | mr = 0170805
 | jstor = 1994208| doi-access = free
 }}
</ref> It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the [[Universal Turing machine#Efficiency|universal Turing machine]].<ref>{{cite journal
| last1        = Hennie
| first1       = F. C.
| last2        = Stearns
| first2       = R. E.
| author-link2  = Richard E. Stearns
|date=October 1966
| title        = Two-Tape Simulation of Multitape Turing Machines
| journal      = J. ACM
| volume       = 13
| issue        = 4
| pages        = 533–546
| location     = New York, NY, USA
| publisher    = ACM
| issn         = 0004-5411
| doi          = 10.1145/321356.321362| s2cid = 2347143
| doi-access= free
}}</ref> 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 [[constructible function|time-constructible function]]s ''f''(''n''),
:<math>\mathsf{DTIME}\left(o\left(f(n)\right)\right) \subsetneq \mathsf{DTIME}(f(n){\log f(n)})</math>,
where [[DTIME]](''f''(''n'')) denotes the complexity class of [[decision problem]]s solvable in time [[big O notation|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 <math>\mathsf{DTIME}(n^a) \subsetneq \mathsf{DTIME}(n^b)</math> if and only if <math>a < b</math>, so we have an infinite time hierarchy.

The time hierarchy theorem for [[nondeterministic Turing machine]]s was originally proven by [[Stephen Cook]] in 1972.<ref>{{cite conference
| title         = A hierarchy for nondeterministic time complexity
| first         = Stephen A.
| last          = Cook
| author-link    = Stephen Cook
| year          = 1972
| conference    = STOC '72
| book-title     = Proceedings of the fourth annual ACM symposium on Theory of computing
| publisher     = ACM
| location      = Denver, Colorado, United States
| pages         = 187–192
| doi           = 10.1145/800152.804913| doi-access= free
}}</ref> It was improved to its current form via a complex proof by Joel Seiferas, [[Michael J. Fischer|Michael Fischer]], and [[Albert R. Meyer|Albert Meyer]] in 1978.<ref>{{cite journal
| last1        = Seiferas
| first1       = Joel I.
| last2        = Fischer
| first2       = Michael J.
| author-link2  = Michael J. Fischer
| last3        = Meyer
| first3       = Albert R.
| author-link3  = Albert R. Meyer
|date=January 1978
| title        = Separating Nondeterministic Time Complexity Classes
| journal      = J. ACM
| volume       = 25
| issue        = 1
| pages        = 146–167
| location     = New York, NY, USA
| publisher    = ACM
| issn         = 0004-5411
| doi          = 10.1145/322047.322061| s2cid = 13561149
| doi-access= free
}}</ref> Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today.<ref>{{cite journal
| first1        = Stanislav
| last1       = Žák
|date=October 1983
| title        = A Turing machine time hierarchy
| journal      = Theoretical Computer Science
| volume       = 26
| issue        = 3
| pages        = 327–333 
| publisher    = Elsevier Science B.V.
| doi          = 10.1016/0304-3975(83)90015-4| doi-access= free
}}</ref> The time hierarchy theorem for nondeterministic Turing machines states that if ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Little O notation|o]](''g''(''n'')), then

:<math>\mathsf{NTIME}(f(n)) \subsetneq \mathsf{NTIME}(g(n))</math>.

The analogous theorems for space are the [[space hierarchy theorem]]s. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of [[advice (complexity)|advice]].<ref>{{Cite book|doi=10.1109/FOCS.2004.33|title=45th Annual IEEE Symposium on Foundations of Computer Science|year=2004|author=Fortnow, L.|pages=316|last2=Santhanam|first2=R.|chapter=Hierarchy Theorems for Probabilistic Polynomial Time|isbn=0-7695-2228-9|s2cid=5555450}}</ref>