Time hierarchy theorem

From Wikipedia, the free encyclopedia

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, for every time-bounded complexity class, there is a strictly larger time-bounded complexity class, and so the run-time hierarchy of problems does not completely collapse. One theorem deals with deterministic computations and the other with non-deterministic ones. The analogous theorems for space are the space hierarchy theorems.

1 Background
2 Proof overview
3 Deterministic time hierarchy theorem
4 Non-deterministic time hierarchy theorem
5 Extensions to other time resources
6 Consequences
7 References

[edit] Background

Both theorems use the notion of a time-constructible function. A function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible if there exists a deterministic Turing machine such that for every $n\in\mathbb{N}$ , if the machine is started with an input of n ones, it will halt after precisely $f (n)$ steps. All polynomials with non-negative integral coefficients are time-constructible, as are exponential functions such as $2 n$ .

[edit] Proof overview

We need to prove that some time class TIME(g(n)) is strictly larger than some time class TIME(f(n)). We do this by constructing a machine which cannot be in TIME(f(n)), by diagonalization. We then show that the machine is in TIME(g(n)), using a simulator machine.

[edit] Deterministic time hierarchy theorem

[edit] Statement

The theorem states that: 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) 2$ . In other words, the complexity class DTIME $f (n)$ is a strict subset of DTIME $f (n) 2$ . Note that $f (n)$ is at least n, since smaller functions are never time-constructible.

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

[edit] Proof

We include here a proof that DTIME(f(n)) is a strict subset of DTIME(f(2n + 1)³) as it is simpler. See the bottom of this section for information on how to extend the proof to f(n)².

To prove this, we first define a language as follows:

$H_f = \left\{ ([M], x)\ |\ M \ \mbox{accepts}\ x \ \mbox{in}\ f(|x|) \ \mbox{steps} \right\}$

Here, M is a deterministic Turing machine, and x is its input (the initial contents of its tape). [M] denotes an input that encodes the Turing machine M. Let m be the size of the tuple ([M], x).

We know that we can decide membership of H_f by way of a deterministic Turing machine that first calculates f(|x|), then writes out a row of 0s of that length, and then uses this row of 0s as a "clock" or "counter" to simulate M for at most that many steps. At each step, the simulating machine needs to look through the definition of M to decide what the next action would be. It is safe to say that this takes at most f(m)³ operations, so

$H_f \in \mathsf{TIME}(f(m)^3)$

The rest of the proof will show that

$H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor ))$

so that if we substitute 2n + 1 for m, we get the desired result. Let us assume that H_f is in this time complexity class, and we will attempt to reach a contradiction.

If H_f is in this time complexity class, it means we can construct some machine K which, given some machine description [M] and input x, decides whether the tuple ([M], x) is in H_f within $\mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor ))$ .

Therefore we can use this K to construct another machine, N, which takes a machine description [M] and runs K on the tuple ([M], [M]), and then accepts only if K rejects, and rejects if K accepts. If now n is the length of the input to N, then m (the length of the input to K) is twice n plus some delimiter symbol, so m = 2n + 1. N's running time is thus $\mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) = \mathsf{TIME}(f( \left\lfloor (2n+1)/2 \right\rfloor )) = \mathsf{TIME}(f(n))$ .

Now if we feed [N] as input into N itself (which makes n the length of [N]) and ask the question whether N accepts its own description as input, we get:

If N accepts [N] (which we know it does in at most f(n) operations), this means that K rejects ([N], [N]), so ([N], [N]) is not in H_f, and thus N does not accept [N] in f(n) steps. Contradiction!
If N rejects [N] (which we know it does in at most f(n) operations), this means that K accepts ([N], [N]), so ([N], [N]) is in H_f, and thus N does accept [N] in f(n) steps. Contradiction!

We thus conclude that the machine K does not exist, and so

$H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )).$

[edit] Extension

The reader may have realised that the proof is simpler because we have chosen a simple Turing machine simulation for which we can be certain that

$H_f \in \mathsf{TIME}(f(m)^3)$

It has been shown [1] that a more efficient model of simulation exists which establishes that

$H_f \in \mathsf{TIME}(f(m) \log f(m))$

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

[edit] Non-deterministic time hierarchy theorem

If g(n) is a time-constructible function, and f(n+1) = 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)).

[edit] Extensions to other time resources

Similar theorems are not known for probabilistic time or quantum time^{[citation needed]}.

[edit] Consequences

The time hierarchy theorems guarantee that the deterministic and non-deterministic version of the exponential hierarchy are genuine hierarchies: in other words P ⊂ EXPTIME ⊂ 2-EXP ⊂ ..., and NP ⊂ NEXPTIME ⊂ 2-NEXP ⊂ ...

The theorem also guarantees that there are problems in P requiring arbitrarily large exponents to solve; in other words, P does not collapse to DTIME(n^k) for any fixed k. For example, there are problems solvable in O(n⁵⁰⁰⁰) time but not O(n⁴⁹⁹⁹) time. This is one argument against considering P to be a practical class of algorithms. This is unfortunate, since if such a collapse did occur, we could deduce that P ≠ PSPACE, since it is a well-known theorem that DTIME(f(n)) is strictly contained in DSPACE(f(n)).

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: whether P and NP, NP and PSPACE, PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.

[edit] References

Stephen Cook (1972). A hierarchy for nondeterministic time complexity. Proceedings of the fourth annual ACM symposium on Theory of computing, pp.187–192.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Pages 310–313 of section 9.1: Hierarchy theorems.
Christos Papadimitriou (1993). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1. Section 7.2: The Hierarchy Theorem, pp.143–146.

Retrieved from "http://en.wikipedia.org../../../t/i/m/Time_hierarchy_theorem.html"

Categories: Articles with unsourced statements since February 2007 | All articles with unsourced statements | Computational complexity theory | Mathematical theorems