Exponential hierarchy
Encyclopedia
In computational complexity theory
, the exponential hierarchy is a hierarchy of complexity class
es, starting with EXPTIME
:
and continuing with
and so on.
We have P
⊂ EXPTIME ⊂ 2-EXPTIME
⊂ 3-EXPTIME ⊂ …. Unlike the analogous case for the polynomial hierarchy
, the time hierarchy theorem
guarantees that these inclusions are proper; that is, there are languages in EXPTIME but not in P, in 2-EXPTIME but not in EXPTIME and so on.
The union of all the classes in the exponential hierarchy is the class ELEMENTARY.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the exponential hierarchy is a hierarchy of complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
es, starting with EXPTIME
EXPTIME
In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
:
and continuing with
and so on.
We have P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
⊂ EXPTIME ⊂ 2-EXPTIME
2-EXPTIME
In computational complexity theory, the complexity class 2-EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
⊂ 3-EXPTIME ⊂ …. Unlike the analogous case for the polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
, the time hierarchy theorem
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...
guarantees that these inclusions are proper; that is, there are languages in EXPTIME but not in P, in 2-EXPTIME but not in EXPTIME and so on.
The union of all the classes in the exponential hierarchy is the class ELEMENTARY.