Time Hierarchy Theorem

The Time Hierarchy Theorem is a foundational result of computational complexity theory stating that a Turing machine given sufficiently more computation time can solve strictly more problems, so that the time-bounded complexity classes form a genuine, non-collapsing hierarchy. First proved for deterministic multi-tape Turing machines by Richard E. Stearns and Juris Hartmanis in 1965, and later extended to nondeterministic Turing machines by Stephen Cook in 1972, the theorem implies for example that problems solvable in n-squared time are not all solvable in n time, and more generally that allowing asymptotically more time to a Turing machine always yields a strictly larger class of solvable problems.