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
In Branch
Proved By
Source Time hierarchy theorem (Wikipedia)
In the Other Atlases
Credited To
Also in Computing Atlas: credited with this subject.
Also in Computing Atlas: credited with this subject.
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.
Proved By: Stephen Cook, Lead
The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972.
In Group: Computability and Complexity Theory, Lead section
In computational complexity theory, the time hierarchy theorems are important
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.