Time hierarchy theorem: Difference between revisions

Revision as of 11:08, 28 June 2005

Revision as of 16:52, 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 ''f''t(''n'')log ''f''(''n'')is grows slower asymptotically than ''g''(''n'')time-constructible, then morethere problemsis cana be solvedlanguage in deterministic timeDTIME(o(t(n)/log ''g''t(''n''))) thanis inproperly timecontained in ''f''DTIME(t(''n'')).[http://www.cs.ubc.ca/~condon/cpsc506/lectures/lec2.pdf] For example, there are problems solvable in time ''n''² but not time ''n'', since ''n'' log ''n'' grows slower asymptotically than ''n''².

===Proof===