Time hierarchy theorem

Time hierarchy theorem
Name	Time hierarchy theorem
Field	Theoretical computer science
Proved by	Juris Hartmanis, Richard E. Stearns
Year	1965
Related	Diagonalization, Computational complexity, Turing machine

Time hierarchy theorem The Time hierarchy theorem is a foundational result in computational complexity theory and theoretical computer science that formalizes how increased time resources permit strictly greater computational power for deterministic and nondeterministic models of computation. It establishes separations between complexity classes defined by different time bounds on abstract machines such as the Turing machine, underpinning later developments in the study of P versus NP problem, space complexity, and resource-bounded reducibility. The theorem originated from work by Juris Hartmanis and Richard E. Stearns and interacts with techniques from diagonalization and models influenced by the Church–Turing thesis.

Introduction

The result emerged in the context of mid-20th century investigations into limits of computation by researchers at institutions like Bell Labs, IBM Research, and universities including Princeton University and the University of California, Berkeley. Hartmanis and Stearns formulated a rigorous framework using deterministic and nondeterministic Turing machine variants and asymptotic notation comparable to later work by Alan Turing and Alonzo Church. The theorem articulates that for appropriately constructible, increasing time functions, the class of problems solvable within one time bound is strictly contained in the class solvable within a larger time bound, yielding separations analogous to those in the Space hierarchy theorem proved in parallel lines of research.

Formal statement

For deterministic computation, the theorem can be stated: if t_1(n) and t_2(n) are time-constructible functions with t_2(n) sufficiently larger than t_1(n) (for example t_2(n) = ω(t_1(n) log t_1(n))), then there exists a language decidable in time O(t_2(n)) that is not decidable in time O(t_1(n)). This formalism situates the theorem among results about classes such as DTIME(t(n)) and class hierarchies related to the P class defined by polynomial bounds, connecting to complexity classes studied at venues like the SIGACT community and conferences including STOC and FOCS. For nondeterministic machines, an analogous separation holds with adjustments for nondeterministic time classes such as NTIME and considerations related to the nondeterministic time hierarchy and its implications for hypotheses like NP ≠ P.

Proof outline

The classical proof employs a diagonalization argument reminiscent of techniques used by Cantor in set theory and by Gödel in incompleteness results, adapted to resource bounds on Turing machine computations. One constructs a language L that, on input encoding of a machine M and size parameter n, simulates M for up to t_1(n) steps and then flips the acceptance outcome, ensuring L cannot be decided within t_1(n) time by any machine in the enumerated family. Ensuring the simulation fits resource bounds requires t_2(n) to be time-constructible and larger than t_1(n) by a margin to account for bookkeeping; similar bookkeeping appears in proofs by Stephen Cook and in separations used in examinations of oracle machines in works by Baker, Gill, and Solovay. The proof also invokes padding arguments and reductions related to frameworks developed in studies at institutions like MIT and Stanford University.

Consequences and corollaries

Immediate corollaries include strict inclusions among classes DTIME(f(n)) for suitably separated functions f, establishing an infinite hierarchy analogous to inequalities in arithmetic hierarchy contexts and yielding separations that inform the structure of P and superpolynomial classes. The theorem implies that if one assumes collapses such as P = EXPTIME, consequences ripple into areas analyzed by researchers at IBM, in texts by Michael Sipser, and in surveys by Richard Lipton. It also provides groundwork for time-space tradeoff results explored in collaborations across institutions including Carnegie Mellon University and Cornell University, and informs complexity-theoretic hardness used in cryptographic protocol analyses by groups at RSA Laboratories.

Variants and extensions

Variants include the nondeterministic time hierarchy, alternation-based hierarchies such as those involving Alternating Turing machine models and classes like EXPTIME versus EXP, and randomized analogues that interact with classes like BPP and hypotheses studied by researchers at Microsoft Research. Extensions use padding techniques to produce separations between resource-bounded classes in the presence of oracles as in results by Baker, Gill, and Solovay and explore uniform versus nonuniform distinctions related to circuit complexity studied by investigators at Princeton University and Caltech. Recent work connects hierarchy theorems to fine-grained complexity landscapes investigated by teams at University of Warsaw and University of California, San Diego.

Examples and applications

Concrete applications include demonstrating that DTIME(n) ⊊ DTIME(n log n) under standard constructibility assumptions, which informs lower bound constructions and completeness results used in textbooks by Christos Papadimitriou, Juris Hartmanis, and Richard E. Stearns. The theorem underlies separations used when proving that certain artificially constructed languages lie outside small time bounds, a method reflected in exercises and results from courses at Harvard University and ETH Zurich. It also supports theoretical underpinnings for complexity separations that influence algorithmic lower bounds considered in algorithmic research at Google Research and in theoretical analyses appearing in proceedings of ICALP and CCC.

Category:Theorems in theoretical computer science