Time hierarchy theorem: Difference between revisions

Revision as of 15:24, 1 June 2004

Revision as of 23:45, 4 July 2004

Line 52:

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

== Non-deterministic time hierarchy theorem ==

===Consequences===

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'')).

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:

===Consequences===

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

The time hierarchy theorems guarantee that the deterministic and non-deterministic version of the [[exponential hierarchy]] are genuine hierarchies: in other words [[Complexity classes P and NP|P]] &sub; [[EXPTIME]] &sub; 2-EXP &sub; ..., and [[NP (complexity)|NP]] &sub; [[NEXPTIME]] &sub; 2-NEXP &sub; ...

However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of [[complexity theory]]: P ?= NP, NP ?= [[PSPACE]], PSPACE ?= EXPTIME, EXPTIME ?= NEXPTIME.

== 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'')).