Time hierarchy theorem: Difference between revisions

Revision as of 19:34, 3 March 2004

Revision as of 19:36, 3 March 2004

Line 8:

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

The proof is not constructive and uses a diagonalization argument.

As a consequence, one can show that the class [[Complexity classes P and NP|'''P''']] is a strict subset of [[EXPTIME]].

===Proof===

Line 54 ⟶ 50:

but since this model of simulation is rather involved, it is not included here.

===Consequences===

=== Non-deterministic time hierarchy theorem ===

As a consequence, one can show that the class [[Complexity classes P and NP|'''P''']] is a strict subset of [[EXPTIME]]., which is defined as:

: <math> \mathsf{EXP} = \bigcup_{k=1}^\infty \mathsf{TIME} (2^{n^k}) </math>

=== Non-deterministic time hierarchy theorem ===

If ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Big O notation|o]](''g''(''n'')), then there exists a decision problem which cannot be solved in non-deterministic time ''f''(''n'') but can be solved in non-deterministic time ''g''(''n''). In other words, the complexity class NTIME(''f''(''n'')) is a strict subset of NTIME(''g''(''n'')).