Time hierarchy theorem

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.

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 polynomials with non-negative integral coefficients are time-constructible, as are exponential functions such as 2ⁿ.

Contents

1 Deterministic time hierarchy theorem 1.1 Statement 1.2 Proof 1.3 Extension 2 Non-deterministic time hierarchy theorem 3 Consequences

Deterministic time hierarchy theorem

Statement

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

Proof

We include here a proof that TIME(f(n)) is a strict subset of TIME(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:

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

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

<math> H_f \in \mathsf{TIME}(f(m)^3) <math>

The rest of the proof will show that

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

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 <math> \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) <math>.

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 <math> \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) = \mathsf{TIME}(f( \left\lfloor (2n+1)/2 \right\rfloor )) = \mathsf{TIME}(f(n)) <math>.

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

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

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

<math> H_f \in \mathsf{TIME}(f(m)^3) <math>

It has been shown [1] (http://www.cs.berkeley.edu/~luca/cs172/noteh.pdf) that a more efficient model of simulation exists which establishes that

<math> H_f \in \mathsf{TIME}(f(m) \log f(m)) <math>

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

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

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 ⊂ ...

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.