Time hierarchy theorem: Difference between revisions

Revision as of 23:07, 9 March 2025

Revision as of 23:09, 9 March 2025

Line 101:

Equivalently, if <math>f, g</math> are time-constructable, and <math>f(n) \ln f(n) = o(g(n))</math>, then

<math display="block">\operatornamemathsf{DTIME}(f(n)) \subsetneq \operatornamemathsf{DTIME} (g(n))   </math></blockquote>

'''Note 1.''' ''f''(''n'') is at least ''n'', since smaller functions are never time-constructible.<br>