Theorem. Time Hierarchy Theorem [time-hierarchy]

Question: is EXP $=$ P? Answer: No!

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

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

Corollary.: $\text{TIME}\left( n^{c} \right) \neq \text{TIME}\left( {n^{4}c} \right)$ for any $c \geq 1$ .
Corollary.: $\text{TIME}\left( n^{c} \right) \neq \text{TIME}\left( 2^{n} \right)$ for any $c \geq 1$ .

$\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”. Come up with a language that the “fast” Turing machines cannot possibly decide, that is decidable by a “slow” machine.

A language that is in EXP and not in P: ???