Nondeterministic time hierarchy theorem: Difference between revisions
(Created page with "==Statement== If <math>f</math> and <math>g</math> are time-constructible functions and <math>f(n + 1) = o(g(n))</math>, then <math>\operatorname{NTIME}(f(n))</math> is stri...") |
(No difference)
|
Latest revision as of 02:38, 28 December 2011
Statement
If and are time-constructible functions and , then is strictly contained in .
