Vipul: Created page with "==Statement== If $f$ and $g$ are time-constructible functions and $f(n + 1) = o(g(n))$ , then $\operatorname{NTIME}(f(n))$ is stri..."

2011-12-28T02:38:48Z

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..."

New page

==Statement==

If <math>f</math> and <math>g</math> are [[time-constructible function]]s and <math>f(n + 1) = o(g(n))</math>, then <math>\operatorname{NTIME}(f(n))</math> is strictly contained in <math>\operatorname{NTIME}(g(n))</math>.

==Related facts==

* [[Deterministic time hierarchy theorem]]
* [[Nondeterministic space hierarchy theorem]]
* [[Deterministic space hierarchy theorem]]

Nondeterministic time hierarchy theorem - Revision history

Vipul: Created page with "==Statement== If f and g are time-constructible functions and f(n + 1) = o(g(n)), then \operatorname{NTIME}(f(n)) is stri..."

Vipul: Created page with "==Statement== If $f$ and $g$ are time-constructible functions and $f(n + 1) = o(g(n))$ , then $\operatorname{NTIME}(f(n))$ is stri..."