Theorem. Time Hierarchy Theorem [time-hierarchy]

Question: is Exp == P (complexity class)? Answer: No!

The time hierarchy theorem tells us that given an f:ℕ→ℕf:{\mathbb{N}}\rightarrow{\mathbb{N}} that is “reasonable” where f(n)=Ω(nlogn)f(n) = \Omega\left( {n\log n} \right), then the TIME(f(n))⊂TIME(f(n)4)\text{TIME}\left( {f(n)} \right) \subset \text{TIME}\left( {f(n)}^{4} \right).

Notably, TIME(f(n))≠TIME(f(n)4)\text{TIME}\left( {f(n)} \right) \neq \text{TIME}\left( {f(n)}^{4} \right)!

Corollary.

TIME(nc)≠TIME(n4c)\text{TIME}\left( n^{c} \right) \neq \text{TIME}\left( {n^{4}c} \right) for any c≥1c \geq 1.

Corollary.

TIME(nc)≠TIME(2n)\text{TIME}\left( n^{c} \right) \neq \text{TIME}\left( 2^{n} \right) for any c≥1c \geq 1.

TIME(2nk)≠TIME\text{TIME}\left( 2^{n^{k}} \right) \neq \text{TIME}

Question. How do you prove the Time hierarchy theorem?

Answer. By diagonalization. Look at Turing machines that are “fast” and Turing machines that are “slow”.

Idea: Look at all Turing machines that run in “fast” time, and come up with a language that they cannot possibly decide.

But we want that language to be decidable by a “slow” Turing machine.

Language that is in EXP and not in P: ???