Time hierarchy theorem: Difference between revisions

Revision as of 23:08, 16 February 2003

Revision as of 03:42, 20 February 2003

Line 1:

In [[computational complexity theory]], the '''time hierarchy theorems''' are important statements that ensure the existence of certain "hard" problems which cannot be solved in a given amount of time. As a consequence, the run-time hierarchy of problems does not completely collapse. One theorem deals with deterministic computations and the other with non-deterministic ones.

Both theorems use the notion of a '''time-constructible function'''. A [[function]] ''f'' : '''N''' → '''N''' is time-constructible if there exists a deterministic [[Turing machine]] such that for every ''n'' in '''N''', if the machine is started with an input of ''n'' ones, it will halt after precisely ''f''(''n'') steps. All [[polynomial]]s with non-negative integral coefficients are time-constructible, as are exponential functions such as 2^''n''. Every time-constructible function ''f''(''n'') satisfies ''f''(''n'') ≥ ''n'' for all ''n''.

=== Deterministic time hierarchy theorem ===