Deterministic Time Hierarchy Theorem

From ProofWiki
Jump to: navigation, search

Theorem

Let $f \left({n}\right)$ be a time-constructible function.

Then there exists a decision problem which:

can be solved in worst-case deterministic time $f \left({2n + 1}\right)^3$

but:

cannot be solved in worst-case deterministic time $f \left({n}\right)$.

In other words, the complexity class $\mathsf{DTIME} \left({ f \left({n}\right) }\right) \subsetneq \mathsf{DTIME} \left({ f \left({2n+1}\right)^3 }\right)$.


Proof

Let $H_f$ be a set defined as follows:

$H_f = \left\{ { \left({ \left[{M}\right], x}\right): \text{$M$ accepts $x$ in $f \left({\left\vert{x}\right\vert}\right)$ steps} }\right\}$

where:

$M$ is a (deterministic) Turing machine
$x$ is its input (the initial contents of its tape)
$\left[{M}\right]$ denotes an input that encodes the Turing machine $M$


Let $m$ be the size of $\left({ \left[{M}\right], x }\right)$.

We know that we can decide membership of $H_f$ by way of a (deterministic) Turing machine that:

$(1): \quad$ calculates $f \left({\left\vert{x}\right\vert}\right)$
$(2): \quad$ writes out a row of $0$s of that length
$(3): \quad$ uses this row of $0$s as a 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 \left({m}\right)^3$ operations, so:

$ H_f \in \mathsf{DTIME} \left({ f \left({m}\right)^3 }\right)$


Now assume:

$H_f \in \mathsf{DTIME} \left({ f \left({ \left\lfloor{ \dfrac m 2 }\right\rfloor }\right) }\right)$

Then we can construct some machine $K$ which:

given some machine description $\left[{M_K} \right]$ and input $x$
decides within $ \mathsf{DTIME} \left({ f \left({ \left\lfloor{ \dfrac m 2 }\right\rfloor }\right) }\right)$ whether $\left({ \left[{ M_K }\right], x }\right) \in H_f$.

Construct another machine $N$ which:

takes a machine description $\left[{M_N}\right]$
runs $K$ on $\left({ \left[{M_N}\right], \left[{M_N}\right] }\right)$
accepts only if $K$ rejects, and rejects if $K$ accepts.


Let $m_n$ be the length of $\left[{M_N}\right]$.

Then $m$ (the length of the input to $K$) is twice $m_n$ plus some delimiter symbol, so:

$ m = 2m_n + 1 $

$N$'s running time is thus:

\(\displaystyle \mathsf{DTIME} \left({f \left({\left\lfloor{\frac m 2}\right\rfloor}\right)}\right)\) \(=\) \(\displaystyle \mathsf{DTIME} \left({f \left({\left\lfloor{\frac{2 m_n + 1} 2}\right\rfloor }\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \mathsf{DTIME} \left({f \left({m_n}\right)}\right)\)


Now consider the case $M_N = N$.

That is we feed $\left[{N}\right]$ as input into $N$ itself).

In this case $m_n$ is the length of $\left[{N}\right]$.


  • If $N$ accepts $\left[{N}\right]$ (which we know it does in at most $f \left( {m_n} \right)$ operations):
    • By the definition of $N$, $K$ rejects $\left({ \left[{N}\right], \left[{N}\right] }\right)$
    • Therefore, by the definition of $K$, $ \left({ \left[{N}\right], \left[{N}\right] }\right) \notin H_f $
    • Therefore, by the definition of $H_f$, $N$ does not accept $\left[{N}\right]$ in $f \left( {m_n} \right)$ steps -- a contradiction.


  • If $N$ rejects $\left[{N}\right]$ (which we know it does in at most $f \left( {m_n} \right)$ operations):
    • By the definition of $N$, $K$ accepts $\left({ \left[{N}\right], \left[{N}\right] }\right)$
    • Therefore, by the definition of $K$, $ \left({ \left[{N}\right], \left[{N}\right] }\right) \in H_f $
    • Therefore, by the definition of $H_f$, $N$ does accept $\left[{N}\right]$ in $f \left( {m_n} \right)$ steps -- a contradiction.


Therefore, $K$ does not exist, and so:

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


Substituting $2n + 1$ for $m$, we get:

$H_f \notin \mathsf{DTIME} \left({f \left({n}\right)}\right)$

and, from the earlier result:

$H_f \in \mathsf{DTIME} \left({f \left({2n+1}\right)^3}\right)$

$\blacksquare$