Revision as of 16:55, 28 June 2005 edit Dcoetzee (talk \| contribs) 37,529 edits →Statement: Fix example to match restatement ← Previous edit		Revision as of 07:46, 29 June 2005 edit undo Timwi (talk \| contribs) Administrators 32,166 edits m →Statement: change t(n) to f(n) since the rest of the article uses that Next edit →
Line 9: 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>). Even more generally, it can be shown that if t''f''(''n'') is time-constructible, then DTIME(~~o(t~~''f''(''n'')/log t''f''(''n)'')) is properly contained in DTIME(t''f''(''n'')). For example, there are problems solvable in time ''n''<sup>2</sup> but not time ''n'', since ''n'' is in oO(''n''<sup>2</sup>/log ''n''<sup>2</sup>). ===Proof===

Time hierarchy theorem: Difference between revisions