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:
“The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.”
—Raymond Chandler (1888–1959)