Content deleted Content added
m typo |
m Open access bot: doi updated in citation with #oabot. |
||
Line 32:
| 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>,
| |||