Proof — Time hierarchy theorem

Statement

For time-constructible functions f(n) and g(n) with f(n) = o(g(n)), there exist problems solvable in time O(g(n)) but not in time O(f(n)). More time allows solving strictly more problems.

Formula

More time ⇒ more problems

Equation

DTIME(f(n)) ⊊ DTIME(g(n)) when f(n) = o(g(n))

Proof sketch

Hartmanis and Stearns introduced complexity theory and proved the time hierarchy theorem using diagonalization. The proof constructs a language that a machine running in time O(g(n)) can decide but no machine running in time O(f(n)) can.