Time hierarchy theorem

ID: time-hierarchy-theorem

The Time Hierarchy Theorem is a fundamental result in computational complexity theory that formalizes the idea that more time allows for the solution of more problems. More specifically, it provides a rigorous framework for understanding how the class of problems that can be solved by deterministic Turing machines in polynomial time expands as the amount of time allowed increases.

New to topics? Read the docs here!