Exponential hierarchy

In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds $2^{cn}$ for a constant c, and full exponential bounds $2^{n^c}$ ), leading to two versions of the exponential hierarchy:^[1]^[2]

EH is the union of the classes $\Sigma^E_k$ for all k, where $\Sigma^E_k=\mathrm{NE}^{\Sigma^P_{k-1}}$ (i.e., languages computable in nondeterministic time $2^{cn}$ for some constant c with a $\Sigma^P_{k-1}$ oracle). One also defines $\Pi^E_k=\mathrm{coNE}^{\Sigma^P_{k-1}}$ , $\Delta^E_k=\mathrm E^{\Sigma^P_{k-1}}$ . An equivalent definition is that a language L is in $\Sigma^E_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,\dots,y_k),

where

R(x,y_1,\dots,y_n)

is a predicate computable in time

2^{c|x|}

(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^{cn}

for some c with constantly many alternations.

EXPH is the union of the classes $\Sigma^{EXP}_k$ , where $\Sigma^{EXP}_k=\mathrm{NEXP}^{\Sigma^P_{k-1}}$ (languages computable in nondeterministic time $2^{n^c}$ for some constant c with a $\Sigma^P_{k-1}$ oracle), and again $\Pi^{EXP}_k=\mathrm{coNEXP}^{\Sigma^P_{k-1}}$ , $\Delta^{EXP}_k=\mathrm{EXP}^{\Sigma^P_{k-1}}$ . A language L is in $\Sigma^{EXP}_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,\dots,y_k),

where

R(x,y_1,\dots,y_k)

is computable in time

2^{|x|^c}

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

2^{n^c}

on an alternating Turing machine with constantly many alternations.

We have E ⊆ NE ⊆ EH ⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, and EH ⊆ EXPH.

References

↑ Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in PH, Theoretical Computer Science 158 (1996), no. 1–2, pp. 221–231.
↑ Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.

External links

Complexity Zoo: Class EH

Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system