Proof Overview
We need to prove that some time class TIME(g(n)) is strictly larger than some time class TIME(f(n)). We do this by constructing a machine which cannot be in TIME(f(n)), by diagonalization. We then show that the machine is in TIME(g(n)), using a simulator machine.
Read more about this topic: Time Hierarchy Theorem
Famous quotes containing the word proof:
“Talk shows are proof that conversation is dead.”
—Mason Cooley (b. 1927)