Time hierarchy theorem

The time hierarchy theorem is a foundational result in computational complexity theory establishing that given more time, a Turing machine can solve strictly more problems. Formally, for any time-constructible function f(n), there exist problems solvable in O(f(n)) time that cannot be solved in o(f(n)/log f(n)) time by any deterministic Turing machine. The theorem is proved by diagonalization: construct a problem that simulates all machines running within the smaller time bound and answers the opposite. This yields strict containments such as P ⊂ EXP, but the required superpolynomial gap means the theorem cannot separate P from NP — the central separation the field craves. The time hierarchy theorem is a proof of abundance, not adjacency: it shows there is plenty of room between exponential time and polynomial time, but says nothing about what lives in the gap.\n\nSee also: Padding argument, Constructible function.