Content deleted Content added
Ascchrvalstr (talk | contribs) m →Proof: Fix typo Tag: possibly inaccurate edit summary |
→top: link DTIME, and briefly explain it, right after 1st use |
||
Line 33:
| doi = 10.1145/321356.321362| s2cid = 2347143
}}</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(\frac{f(n)}{\log f(n)}\right)\right) \subsetneq \mathsf{DTIME}(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 time hierarchy theorem for [[nondeterministic Turing machine]]s was originally proven by [[Stephen Cook]] in 1972.<ref>{{cite conference
| |||