Computational Complexity HT25, Hierarchy theorems

Created: May 12, 2025 | Updated: June 01, 2025 | About these notes | View in context | Study these flashcards

Flashcards

Time hierarchy theorem

@State the time hierarchy theorem.

Suppose:

  • $T, T’ : \mathbb N \to \mathbb N$ are time bounds
  • $T, T’$ are time constructible
  • $T\log T = o(T’)$

Then:

\[\mathsf{DTIME}(T) \subsetneq \mathsf{DTIME}(T')\]

@Prove the time hierarchy theorem, i.e. that if

Suppose:

  • $T, T’ : \mathbb N \to \mathbb N$ are time bounds
  • $T’$ is time constructible
  • $T(n)\log T(n) = o(T’(n))$

Then:

\[\mathsf{DTIME}(T) \subsetneq \mathsf{DTIME}(T')\]

Let $\langle M \rangle$ denote the string representation of a TM, and define $\mu : \Sigma^\ast \to \{\text{TM}s\}$ which maps strings to Turing machines by:

\[\mu(x) = \begin{cases} M &\text{if } x \text{ is of the form } \langle M \rangle 01^i \text{ for some }i \\\\ \bot &\text{otherwise, where this is the TM that always halts} \end{cases}\]

Note that each Turing machine has infinitely many strings that map to it.

Consider the table with strings $s _ j$ as rows and Turing machines $M _ i := \mu(s _ i)$ as rows. Construct a Turing machine $D$ which on input $x _ i$ does the following:

  • Read $x _ i$.
  • Computes $T’( \vert x _ i \vert )$ (using the assumption $T’$ is time constructible)
  • Compute $M _ i = \mu(x _ i)$.
  • Run $\mathcal U$ on $\langle M _ i, x\rangle$ for at most $T’( \vert x _ i \vert )$ steps.
    • $\mathcal U$ is an “efficient enough” universal Turing machine
    • Since $T’$ is time constructible, $D$ can run in time $O(T’( \vert x _ i \vert ))$ by writing down $T’( \vert x _ i \vert )$ zeroes on a work tape and then erasing them for each step of the simulation by $\mathcal U$.
    • Since $T\log T = o(T’)$, if $M _ i$ terminates within $T( \vert x _ i \vert )$ steps, $\mathcal U$ can fully simulate $M _ i$ in $O(T’( \vert x _ i \vert ))$ steps.
  • Two cases:
    • All zeroes are erased (“the clock runs out”): $D$ rejects.
    • $M _ i$ is simulated before zeroes are erased: $D$ outputs the opposite of $M _ i$.

By construction, $D$ runs in time $O(T’)$ and can diagonalise against all $O(T)$ Turing machines. Since we want to show that $\mathsf{DTIME}(T) \subsetneq \mathsf{DTIME}(T’)$, suppose that $L(D)$ could also be decided in $O(T)$ time. But then the encoding of this $O(T)$ Turing machine would appear as one of the rows. Then $D$ would disagree with this Turing machine on the diagonal, a contradiction.

(Since every Turing machine has infinitely many encodings, we can always pick $i$ large enough so that it is fully simulated with an arbitrarily large constant in the big-O notation).

Space hierarchy theorem

@State the space hierarchy theorem.

Suppose:

  • $S, S’ : \mathbb N \to \mathbb N$ are time bounds
  • $S’$ is space constructible
  • $S = o(S’)$

Then:

\[\mathsf{DSPACE}(S) \subsetneq \mathsf{DSPACE}(S')\]

@State a result about the existence of efficient universal Turing machines.

There exists a universal Turing machine $\mathcal U$ such that if:

  • $M$ is a Turing machine
  • $M$ has time bound $t _ M$
  • $M$ has space bound $s _ M(n)$
  • $x$ is an input, $n = \vert x \vert $

Then:

  • $\mathcal U$ uses $O( \vert \langle M \rangle \vert \cdot t _ M(n) \log t _ M(n))$ time simulating $M$ on $x$
  • $\mathcal U$ uses $O( \vert \langle M \rangle \vert \cdot s _ M(n))$ space simulating $M$ on $x$

Nondeterministic hierarchy theorems

Nondeterministic versions of the above theorems also hold under slightly different assumptions. The proofs above don’t quite go through in the nondeterministic case because of the difficulty of telling when a nondeterministic machine has rejected so that we can flip the answer: Since we would have to e.g. simulate a $\mathsf{NTIME}(n)$ machine using a $\mathsf{NTIME}(n^2)$ machine, to verify that the $\mathsf{NTIME}(n)$ machine rejects we would actually need to check all the nondeterministic branches.

Applications

Proof by contradiction

One common application of the these hierarchy theorems is in proof by contradiction. Consider the following question:

Consider the language $L$ consisting of all pairs $\langle \tilde M, w \rangle$ such that $M$ is a deterministic Turing machine and $w \in {0, 1}^\ast$, and moreover $M$ accepts $w$ within $ \vert w \vert ^2$ steps. Show that $L \notin \mathsf{DTIME}(n)$.

One approach is to show that $L$ is hard for $\mathsf{DTIME}(n^{3/2})$. Then if $L \in \mathsf{DTIME}(n)$, this would contradict the time hierarchy theorem (why $n^{3/2}$ instead of $n^2$? this is to deal with asymptotic constants).

Examples

What’s the rough idea behind the proof that

\[\mathsf P \ne \mathsf{DTIME}(2^n)\]

?

Applying the time hierarchy theorem to each $\mathsf{DTIME}(n^k)$ doesn’t quite work, since you’d up needing to conclude something like the union over proper subsets is also proper. Hence you instead show

\[\mathsf P \subseteq \mathsf{DTIME}(n^{\log n}) \subsetneq \mathsf{DTIME}(2^n)\]

by applying the time hierarchy theorem with $n^{\log n}$ and $2^n$, and using the fact that every polynomial is eventually dominated by $n^{\log n}$.



Related posts