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:
“In the reproof of chance
Lies the true proof of men.”
—William Shakespeare (1564–1616)