Hierarchy Theorems (Time, Space, Alternation)

There are many hierarchy theorems based on Time, Space, Nondeterminism, Randomization etc.

Time Hierarchy Theorem (Version 1): If $f, g$ are time-constructible functions satisfying $f(n) \log f(n)=o(g(n))$, then $$ DTIME(f(n)) \subsetneq DTIME (g(n)) $$

Proof: Consider the following Turing machine $D$: "On input $x$, run for $f(|x|)\log (f(|x|))$ steps the Universal $TM$ $\mathcal{U}$ to simulate the execution of $M_x$ on $x$. If $\mathcal{U}$ outputs some bit $b \in\{0,1\}$ in this time, then output the opposite answer (i.e., output $1-b$ ). Else output 0.” Here $M_x$ is the machine represented by the string $x$.

    By definition, $D$ halts within $f(n)\log (f(n))$ steps and hence the language $L$ decided by $D$ is in $DTIME(g(n))$.

Claim: $L \notin$ DTIME $(f(n))$

Proof: For contradiction's sake, assume that there is some $TM$ $M$ and constant $c$ such that $TM$ $M$, given any input $x \in\{0,1\}^*$, halts within $cf(|x|)$ steps and outputs $D(x)$.

    The time to simulate $M$ by the universal Turing machine $\mathcal{U}$ on every input $x$ is at most $c^{\prime} cf(|x|) \log(f( |x|))$ for some number $c^{\prime}$ that depends on the alphabet size and number of tapes and states of $M$ but is independent of $|x|$. There is some number $n_0$ such that $f(n)\log (f(n))>n$ for every $n \geq n_0$. Let $x$ be a string representing the machine $M$ whose length is at least $n_0$ (such a string exists since $M$ is represented by infinitely many strings). Then, $D(x)$ will obtain the output $b=M(x)$ within $f(|x|)\log (f(|x|))$ steps, but by definition of $D$, we have $D(x)=1-b \neq M(x)$. Thus we have derived a contradiction.

Hence $L \notin$ DTIME $(f(n))$ but $L \in$ DTIME $(g(n))$ where $f(n)\log (f(n))=o(g(n))$. Hence $$ DTIME(f(n)) \subsetneq DTIME (g(n)) $$ $\blacksquare$

Time Hierarchy Theorem (Version 2): For any time constructible function $t:\mathbb{N}\to \mathbb{N}$ a language exists that is decidable in $O(t(n))$ time but is not decidable in time $o\left(  \frac{t(n)}{\log (t(n))}\right)$

Proof: PRoof The following $O(t(n))$ time algorithm $D$ decides a language $A$ that is not decidable in $o\left(\frac{t(n)}{\log( t(n))}\right)$ time. $D=$ "On input $w$ :

1. Let $n$ be the length of $w$.
2. Compute $t(n)$ using time constructibility and store the value $\left\lceil \frac{t(n)}{\log( t(n))}\right\rceil$ in a binary counter. Decrement this counter before each step used to carry out stages 4 and 5. If the counter ever hits 0, reject.
3. If $w$ is not of the form $\langle M\rangle 10^*$ for some TM $M$, reject.
4. Simulate $M$ on $w$.
5. If $M$ accepts, then reject. If $M$ rejects, then accept."

[Same kind of turning machine construction as in version 1]

We'll show that $A$ is not decidable in $o\left(\frac{t(n)}{\log( t(n))}\right)$ time. Assume to the contrary that TM $M$ decides $A$ in time $g(n)$, where $g(n)$ is $o\left(\frac{t(n)}{\log( t(n))}\right)$. Here, $D$ can simulate $M$, using time $d g(n)$ for some constant $d$. If the total simulation time (not counting the time to update the step counter) is at most $\frac{t(n)}{\log( t(n))}$, the simulation will run to completion. Because $g(n)$ is $o\left(\frac{t(n)}{\log( t(n))}\right)$, some constant $n_0$ exists where $d g(n)<\frac{t(n)}{\log( t(n))}$ for all $n \geq n_0$. Therefore, $D$ 's simulation of $M$ will run to completion as long as the input has length $n_0$ or more. Consider what happens when we run $D$ on input $\langle M\rangle 10^{n_0}$. This input is longer than $n_0$, so the simulation in stage 4 will be complete. Therefore, $D$ will do the opposite of $M$ on the same input. Hence $M$ doesn't decide $A$, which contradicts our assumption. Therefore, $A$ is not decidable in $o\left(\frac{t(n)}{\log( t(n))}\right)$ time. $\blacksquare$