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 fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.”
—Charles Baudelaire (1821–1867)