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. The analogous theorems for space are the space hierarchy theorems.

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

Deterministic time hierarchy theorem

Statement

For any time constructible function ${\displaystyle t:N\rightarrow N}$ , there exists a language ${\displaystyle A}$  that is decidable in time ${\displaystyle O(t(n))}$  but not in time ${\displaystyle o(t(n)/\log t(n))}$ .

Proof

We prove this by constructing a Turing machine ${\displaystyle B}$  that is a ${\displaystyle O(t(n))}$  decider for a language ${\displaystyle A}$  that is not decidable in ${\displaystyle o(t(n)/\log t(n))}$  time. In order to ensure that ${\displaystyle B}$  finishes its computation in time ${\displaystyle O(t(n))}$  we include in ${\displaystyle B}$  a counter of length ${\displaystyle \log t(n)}$ , which is the number of bits required to store the number ${\displaystyle O(t(n))}$ .

There are two parts to this construction. One part is to ensure that ${\displaystyle B}$  has a different output from all ${\displaystyle o(t(n)/\log t(n))}$  Turing machines. We do this by simulating a given Turing machine ${\displaystyle M}$  on input ${\displaystyle \langle M\rangle 10^{*}}$ . If ${\displaystyle M}$  finishes its computation quickly enough (in time less than ${\displaystyle t(n)/\log t(n)}$  where ${\displaystyle n}$  is the length of the input string), we construct ${\displaystyle B}$  to have the opposite output (this is similar to the digitalisation technique explained in the Diagonalization Lemma). But what if ${\displaystyle M}$  does not halt in the alloted time? we still need to make sure that ${\displaystyle B}$  is a ${\displaystyle O(t(n))}$  decider, so we add a counter to ${\displaystyle B}$  to make sure that it stops after ${\displaystyle t(n)}$  steps.

The basic structure of TM ${\displaystyle B}$  is:

input: string ${\displaystyle w}$  with length ${\displaystyle n}$ 
if w 6 ${\displaystyle w\not =\langle M\rangle 10^{*}}$  for some TM M then
  reject
end if
calculate ${\displaystyle \lceil t(n)/\log t(n)\rceil }$  and use this value to create counter ${\displaystyle c}$ 
while c > 0 do
  simulate ${\displaystyle M}$  with input ${\displaystyle w}$  for 1 step
  if ${\displaystyle M}$  accepts then
    reject
  else if ${\displaystyle M}$  rejects then
    accept
  end if
  decrement ${\displaystyle c}$ 
end while
reject

Now we need to show that ${\displaystyle B}$  halts within ${\displaystyle O(t(n))}$  time. In order to simulate ${\displaystyle M}$ , ${\displaystyle B}$  needs to keep track of ${\displaystyle M}$ 's state, the tape symbol ${\displaystyle M}$  is currently reading, and ${\displaystyle M}$ 's transition function. If ${\displaystyle B}$  were to store this information in one spot on its tape, as ${\displaystyle B}$  simulates ${\displaystyle M}$  ${\displaystyle B}$  may have to spend an arbitrary amount of time moving traveling back and forth retrieving this information about ${\displaystyle M}$ . So we introduce a notion of tracks on ${\displaystyle B}$ 's tape. In one track we will store information about ${\displaystyle M}$ , in the other track we will store information about ${\displaystyle B}$ 's current computation. We change ${\displaystyle B}$ 's tape alphabet to a set of pairs, one from each track. Then, in a constant amount of time (dependent on the length of ${\displaystyle M}$ , not the length of the entire input string ${\displaystyle w}$ ) ${\displaystyle B}$  can copy the information on the first track to the current ___location on the second track. So, if ${\displaystyle M}$  runs in time ${\displaystyle g(n)}$ , ${\displaystyle B}$  can simulate it in time ${\displaystyle O(g(n))}$ . We add the counter to a third tape (also to cut down on unbounded time of traveling between the current head position of ${\displaystyle B}$  and the clock). The actual clock updating operations require only ${\displaystyle O(\log t(n))}$  because the length of the clock is ${\displaystyle \log(t(n)/\log t(n))}$ . So, if we allow ${\displaystyle B}$  to execute for ${\displaystyle \lceil t(n)/\log t(n)\rceil }$  steps and each step requires ${\displaystyle O(\log t(n))}$  time, ${\displaystyle B}$  will halt in time ${\displaystyle O(t(n))}$ .

Formally we need to show that ${\displaystyle A}$  is not decidable in ${\displaystyle o(t(n)/\log t(n))}$  time. We prove this by contradiction. Assume that TM ${\displaystyle M}$  decides ${\displaystyle A}$  in time ${\displaystyle g(n)}$ , which is ${\displaystyle o(t(n)/\log t(n))}$ . Then ${\displaystyle B}$  can simulate ${\displaystyle M}$  in ${\displaystyle d\cdot g(n)}$  time for some constant ${\displaystyle d}$ . So, for some constant ${\displaystyle n_{0}}$ , ${\displaystyle d\cdot g(n)<t(n)/\log t(n)}$  for all ${\displaystyle n\geq n_{0}}$ . Consider what happens when we run ${\displaystyle B}$  on input ${\displaystyle \langle M\rangle 10^{n_{0}}}$ . This input is longer than ${\displaystyle n_{0}}$ , which means that ${\displaystyle B}$  will have time to simulate ${\displaystyle M}$  until it halts and then ${\displaystyle B}$  will do the opposite of ${\displaystyle M}$  on the same input. Thus, ${\displaystyle M}$  does not decide ${\displaystyle A}$  which contradicts our assumption. So, ${\displaystyle A}$  is not decidable in ${\displaystyle o(t(n)/\log t(n))}$  time.

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

Corollaries

Corrollary 1

For any two functions ${\displaystyle t_{1}}$ , ${\displaystyle t_{2}:\mathbb {N} \longrightarrow \mathbb {N} }$ , where ${\displaystyle t_{1}}$ (n) is o(${\displaystyle t_{2}}$ (n)/${\displaystyle logt_{2}}$ (n)) and ${\displaystyle t_{2}}$  is time constructible, TIME(${\displaystyle t_{1}}$ (n)) ${\displaystyle \subset }$  TIME(${\displaystyle t_{2}}$ (n)).

This corollary shows that ${\displaystyle t_{1}}$  and ${\displaystyle t_{2}}$  belong to two different classes of TIME hierarchies (and that TIME(${\displaystyle t_{2}}$ ) includes TIME(${\displaystyle t_{1}}$ ). Note that we can say the two classes are different because TIME(${\displaystyle t_{1}}$ ) is a strict subset of TIME(${\displaystyle t_{2}}$ ).

Corrollary 2

For any two real number ${\displaystyle 1\leq \epsilon _{1}<\epsilon _{2}}$ , TIME(${\displaystyle n^{\epsilon _{1}}}$ ) ${\displaystyle \subset }$  TIME(${\displaystyle n^{\epsilon _{2}}}$ )

This corollary shows that polynomials of different degree are in different TIME hierarchies and that the classes of the smaller degree polynomials are strict subsets of the classes of the larger degree polynomials.

Corrollary 3

${\displaystyle P\subset EXPTIME}$ 

By this corollary, the classes of polynomial time algorithms and exponential time algorithms are different.

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.