Time hierarchy theorem: Difference between revisions

Revision as of 20:13, 6 February 2007

Revision as of 10:56, 9 February 2007

Line 12:

===Statement===

The theorem states that: If <math>f(n)</math> is a time-constructible function, then there exists a [[decision problem]] which cannot be solved in worstbest-case deterministic time <math>f(n)</math> but can be solved in worst-case deterministic time <math>f(n)^2</math>. In other words, the complexity class [[DTIME]]<math>f(n)</math> is a strict subset of DTIME<math>f(n)^2</math>. Note that <math>f(n)</math> is at least ''n'', since smaller functions are never time-constructible.

Even more generally, it can be shown that if <math>f(n)</math> is time-constructible, then <math>\operatorname{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right)</math> is properly contained in <math>\operatorname{DTIME}(f(n))</math>. For example, there are problems solvable in time ''n''² but not time ''n'', since ''n'' is in <math>o\left(\frac{n^2}{\log {n^2}}\right)</math>.