computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, the exponential hierarchy is a hierarchy of

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...

es, which is an

exponential time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

analogue of the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...

. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds

2^

for a constant ''c'', and full exponential bounds

2^

), leading to two versions of the exponential hierarchy.Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122. This hierarchy is sometimes also referred to as the ''weak'' exponential hierarchy, to differentiate it from the ''strong'' exponential hierarchy.

EH

EH is the union of the classes

\Sigma^\mathsf_k

for all ''k'', where

\Sigma^\mathsf_k=\mathsf^

(i.e., languages computable in nondeterministic time

2^

for some constant ''c'' with a

\Sigma^\mathsf_

oracle). One also defines :

\Pi^\mathsf_k=\mathsf^, \Delta^\mathsf_k=\mathsf^.

An equivalent definition is that a language ''L'' is in

\Sigma^\mathsf_k

if and only if it can be written in the form :

x\in L\iff\exists y_1\forall y_2\dots Qy_k R(x,y_1,\ldots,y_k),

where

R(x,y_1,\ldots,y_n)

is a predicate computable in time

2^

(which implicitly bounds the length of ''y_i''). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time

2^

for some ''c'' with constantly many alternations.

EXPH

EXPH is the union of the classes

\Sigma^_k

, where

\Sigma^_k=\mathsf^

(languages computable in nondeterministic time

2^

for some constant ''c'' with a

\Sigma^\mathsf_

oracle), and again: :

\Pi^_k=\mathsf^, \Delta^_k=\mathsf^.

A language ''L'' is in

\Sigma^_k

if and only if it can be written as :

x\in L\iff\exists y_1 \forall y_2 \dots Qy_k R(x,y_1,\ldots,y_k),

where

R(x,y_1,\ldots,y_k)

is computable in time

2^

for some ''c'', which again implicitly bounds the length of ''y_i''. Equivalently, EXPH is the class of languages computable in time

2^

on an alternating Turing machine with constantly many alternations.

Comparison

: E ⊆ NE ⊆ EH⊆

ESPACE Espace may refer to: * ESPACE, a complexity class in computational complexity theory * Espace musique, a Canadian radio service * Espace 2, a Swiss radio station * Radio Espace, a French radio station *Espace Group, a French media company *Group Es ...

, :

EXP Exp may stand for: * Exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the pos ...

⊆

NEXP In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^. In terms of NTIME, :\mathsf = \bigcup_ \mathsf(2^) ...

⊆ EXPH⊆ EXPSPACE, :EH ⊆ EXPH.

References

External links

{{DEFAULTSORT:Exponential Hierarchy Complexity classes