Content deleted Content added
An anonymous user replaced the entire proof with one which I (personally) find less clear and which uses notation without defining it. Hence, revert. Please discuss on talk page if you disagree. |
→Statement: little note, suggested on talk page |
||
Line 7:
===Statement===
The theorem states that: If ''f''(''n'') is a time-constructible function, 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>). Note that ''f''(''n'') is at least ''n'', since smaller functions are never time-constructible.
Even more generally, it can be shown that if ''f''(''n'') is time-constructible, then DTIME(o(''f''(''n'')/log ''f''(''n''))) is properly contained in DTIME(''f''(''n'')). For example, there are problems solvable in time ''n''<sup>2</sup> but not time ''n'', since ''n'' is in o(''n''<sup>2</sup>/log ''n''<sup>2</sup>).
| |||