Time hierarchy theorem

The Time Hierarchy Theorem is a fundamental result in computational complexity theory that establishes a formal relationship between the resources (specifically, time) needed by different classes of algorithms to solve computational problems. It essentially says that given more computational time, a Turing machine can solve more problems, thus creating a “hierarchy” of complexity classes.

Statement of the Time Hierarchy Theorem

The Time Hierarchy Theorem has two main versions: one for deterministic machines and one for nondeterministic machines. The deterministic version is the most commonly discussed.

Deterministic Time Hierarchy Theorem

Let and be two time-constructible functions such that:

• = .

Then there exists a language (a set of strings over some alphabet) that can be decided by a deterministic Turing machine in time , but not in time .

In simpler terms:

• There exists a problem that can be solved within time but cannot be solved in time , where is asymptotically larger than .

Nondeterministic Time Hierarchy Theorem

A similar result holds for nondeterministic Turing machines. Let and be time-constructible functions such that:

• = .

Then there exists a language that can be decided by a nondeterministic Turing machine in time , but not in time .

Implications of the Theorem

1. Strict Hierarchy: The theorem implies a strict hierarchy of complexity classes based on time. For example, there exist problems that can be solved in time that cannot be solved in time by any deterministic algorithm.
2. P vs. EXPTIME: A corollary of the theorem is that , meaning that the class of problems solvable in polynomial time is strictly smaller than the class of problems solvable in exponential time.
3. Gap Between Complexity Classes: It formally shows that increasing the time bound allows us to solve more complex problems, even if the increase in time is relatively modest (as long as it meets the conditions specified in the theorem).

Proof Outline (Sketch)

The proof of the Time Hierarchy Theorem involves constructing a language that can be decided by a Turing machine running in time but not in time . This is done by designing a language that simulates every machine running in time and then diagonalizes against these machines (i.e., constructs a language that differs from the output of these machines on some input). The diagonalization process ensures that the language cannot be decided by any machine running in time , but can be decided in time .

Conclusion

The Time Hierarchy Theorem is a cornerstone result in complexity theory, establishing that more time means more computational power, and thus more complex problems can be solved. It provides a foundational understanding of how complexity classes are structured and the limitations of algorithms operating within certain time bounds.