Revision as of 14:50, 16 May 2004 edit Charles Matthews (talk \| contribs) Autopatrolled, Administrators 367,786 edits m =Non-deterministic time hierarchy theorem= lk ← Previous edit		Revision as of 13:06, 18 May 2004 edit undo Gdr (talk \| contribs) Extended confirmed users 29,064 edits m =Statement= link Next edit →
Line 7: ===Statement=== 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\|TIME]](''f''(''n'')) is a strict subset of TIME(''f''(''n'')<sup>2</sup>). ===Proof===

Time hierarchy theorem: Difference between revisions