Time hierarchy theorem: Difference between revisions

Revision as of 00:16, 23 March 2004

Revision as of 03:31, 13 April 2004

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 determininsticdeterministic time ''f''(''n'')². In other words, the complexity class TIME(''f''(''n'')) is a strict subset of TIME(''f''(''n'')²).

===Proof===