Content deleted Content added
special case |
|||
Line 1:
{{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
Line 35:
}}</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'')).
In particular, this shows that <math>\mathsf{DTIME}(n^a) \subsetneq \mathsf{DTIME}(n^b)</math> if and only if <math>a < b</math>, and we have infinitely many time hierarchies.
| |||