Content deleted Content added
→Consequences: P does not collapse |
→Statement: and is at least ''n'' (I think we need this assumption) |
||
Line 7:
===Statement===
If ''f''(''n'') is a time-constructible function and is at least ''n'', then there exists a [[decision problem]] which cannot be solved in worst-case deterministic time ''f''(''n'') but can be solved in worst-case deterministic time ''f''(''n'')<sup>2</sup>. In other words, the complexity class [[DTIME]](''f''(''n'')) is a strict subset of DTIME(''f''(''n'')<sup>2</sup>).
Even more generally, it can be shown that if ''f''(''n'')log ''f''(''n'') grows slower asymptotically than ''g''(''n''), then more problems can be solved in deterministic time ''g''(''n'') than in time ''f''(''n'').[http://www.cs.ubc.ca/~condon/cpsc506/lectures/lec2.pdf] For example, there are problems solvable in time ''n''<sup>2</sup> but not time ''n'', since ''n'' log ''n'' grows slower asymptotically than ''n''<sup>2</sup>.
| |||