Content deleted Content added
→Consequences: disambiguation |
|||
Line 12:
===Statement===
The theorem states that: If <math>f(n)</math> is a time-constructible function, then there exists a [[decision problem]] which cannot be solved in worst-case deterministic time <math>f(n)</math> but can be solved in worst-case deterministic time <math>f(n)^2</math>. In other words, the complexity class [[DTIME]]<math>f(n)</math> is a strict subset of DTIME <math>f(n)^2</math>. Note that <math>f(n)</math> is at least ''n'', since smaller functions are never time-constructible.
Even more generally, it can be shown that if <math>f(n)</math> is time-constructible, then <math>\operatorname{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right)</math> is properly contained in <math>\operatorname{DTIME}(f(n))</math>. For example, there are problems solvable in time ''n''<sup>2</sup> but not time ''n'', since ''n'' is in <math>o\left(\frac{n^2}{\log {n^2}}\right)</math>.
| |||