Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time. The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the Universal Turing machine. Consequent to the theorem, for every deterministic time-bounded complexity class, there is a strictly larger time-bounded complexity class, and so the time-bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time-constructible functions f(n), where DTIME(f(n)) denotes the complexity class of decision problems solvable in time O(f(n)). Note that the left-hand class involves little o notation, referring to the set of decision problems solvable in asymptotically less than f(n) time. The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972. It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978. Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time-constructible function, and f(n+1) = o(g(n)), then The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of advice. Both theorems use the notion of a time-constructible function. A function is time-constructible if there exists a deterministic Turing machine such that for every , if the machine is started with an input of n ones, it will halt after precisely f(n) steps.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (21)

Related people (2)

Related units (1)

Related concepts (5)

Related courses (1)

Related lectures (15)

Supporting Teachers' Orchestration in Robot-mediated Classrooms

Sina Shahmoradi

To bring educational robots to classrooms, we need to consider teachers' self-efficacy and challenges in managing a robot-mediated classroom, and how to support them in overcoming these challenges. Orchestration tools are designed to support teachers by pr ...

EPFL2023

Polynomial-time universality and limitations of deep learning

Emmanuel Abbé

The goal of this paper is to characterize function distributions that general neural networks trained by descent algorithms (GD/SGD), can or cannot learn in polytime. The results are: (1) The paradigm of general neural networks trained by SGD is poly-time ...

WILEY2023

Adaptive isogeometric methods with C-1 (truncated) hierarchical splines on planar multi-patch domains

Rafael Vazquez Hernandez

Isogeometric analysis is a powerful paradigm which exploits the high smoothness of splines for the numerical solution of high order partial differential equations. However, the tensor-product structure of standard multivariate B-spline models is not well s ...

WORLD SCIENTIFIC PUBL CO PTE LTD2023

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.

Ce cours aborde les concepts fondamentaux de la programmation et de la programmation orientée objet (langage JAVA). Il permet également de se familisarier avec un environnement de développement inform

Decomposition: Evaluation and New Forms CS-210: Functional programming

Explores decomposition in programming through evaluating expressions and adding new forms, emphasizing object-oriented solutions and the trade-offs involved.

Complexity Theory: P and NP CS-119(c): Information, Computation, Communication

Explores complexity classes P and NP, practical algorithms, non-polynomial problems, and efficient solution verification.

Complexity of Algorithms: Growth and Laws CS-101: Advanced information, computation, communication I

Covers the growth of functions and time complexity analysis for search algorithms.