In computational complexity theory

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.