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.
Facts
StatementIf f(n) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time o(f(n)) but can be solved in worst-case deterministic time O(f(n) log f(n)). 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Sources
1. Time hierarchy theorem (Wikipedia)
Deterministic time hierarchy theorem
then there exists a decision problem which cannot be solved in worst-case deterministic time
History
The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.