Time hierarchy theorem: Difference between revisions

Revision as of 16:52, 28 June 2005

Revision as of 16:53, 28 June 2005

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

Even more generally, it can be shown that if t(n) is time-constructible, then there is a language in DTIME(o(t(n)/log t(n))) is properly contained in DTIME(t(n)). For example, there are problems solvable in time ''n''² but not time ''n'', since ''n'' log ''n'' grows slower asymptotically than ''n''².

===Proof===