Content deleted Content added
Strattemier (talk | contribs) |
→Deterministic time hierarchy theorem: equivalent statement |
||
Line 98:
===Statement===
<blockquote>'''Time Hierarchy Theorem.''' If ''f''(''n'') is a time-constructible function, then there exists a [[decision problem]] which cannot be solved in worst-case deterministic time ''o''(''f''(''n'')) but can be solved in worst-case deterministic time ''O''(''f''(''n'')log ''f''(''n'')). Thus
:<math>\mathsf{DTIME}(o(f(n))) \subsetneq \mathsf{DTIME}\left (f(n)\log f(n) \right).</math
Equivalently, if <math>f, g</math> are time-constructable, and <math>f(n) \ln f(n) = o(g(n))</math>, then
<math display="block">\operatorname{DTIME}(f(n)) \subsetneq \operatorname{DTIME}(g(n)) </math></blockquote>
'''Note 1.''' ''f''(''n'') is at least ''n'', since smaller functions are never time-constructible.<br>
| |||