# 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 ${\displaystyle 2^{cn}}$ for a constant c, and full exponential bounds ${\displaystyle 2^{n^{c}}}$), leading to two versions of the exponential hierarchy:[1][2]

• EH is the union of the classes ${\displaystyle \Sigma _{k}^{E}}$ for all k, where ${\displaystyle \Sigma _{k}^{E}=\mathrm {NE} ^{\Sigma _{k-1}^{P}}}$ (i.e., languages computable in nondeterministic time ${\displaystyle 2^{cn}}$ for some constant c with a ${\displaystyle \Sigma _{k-1}^{P}}$ oracle). One also defines ${\displaystyle \Pi _{k}^{E}=\mathrm {coNE} ^{\Sigma _{k-1}^{P}}}$, ${\displaystyle \Delta _{k}^{E}=\mathrm {E} ^{\Sigma _{k-1}^{P}}}$. An equivalent definition is that a language L is in ${\displaystyle \Sigma _{k}^{E}}$ if and only if it can be written in the form
${\displaystyle x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{k}\,R(x,y_{1},\dots ,y_{k}),}$
where ${\displaystyle R(x,y_{1},\dots ,y_{n})}$ is a predicate computable in time ${\displaystyle 2^{c|x|}}$ (which implicitly bounds the length of yi). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time ${\displaystyle 2^{cn}}$ for some c with constantly many alternations.
• EXPH is the union of the classes ${\displaystyle \Sigma _{k}^{\mathrm {EXP} }}$, where ${\displaystyle \Sigma _{k}^{\mathrm {EXP} }=\mathrm {NEXP} ^{\Sigma _{k-1}^{P}}}$ (languages computable in nondeterministic time ${\displaystyle 2^{n^{c}}}$ for some constant c with a ${\displaystyle \Sigma _{k-1}^{P}}$ oracle), and again ${\displaystyle \Pi _{k}^{\mathrm {EXP} }=\mathrm {coNEXP} ^{\Sigma _{k-1}^{P}}}$, ${\displaystyle \Delta _{k}^{\mathrm {EXP} }=\mathrm {EXP} ^{\Sigma _{k-1}^{P}}}$. A language L is in ${\displaystyle \Sigma _{k}^{\mathrm {EXP} }}$ if and only if it can be written as
${\displaystyle x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{k}\,R(x,y_{1},\dots ,y_{k}),}$
where ${\displaystyle R(x,y_{1},\dots ,y_{k})}$ is computable in time ${\displaystyle 2^{|x|^{c}}}$ for some c, which again implicitly bounds the length of yi. Equivalently, EXPH is the class of languages computable in time ${\displaystyle 2^{n^{c}}}$ on an alternating Turing machine with constantly many alternations.

We have ENE ⊆ EH ⊆ ESPACE, EXPNEXP ⊆ EXPH ⊆ EXPSPACE, and EH ⊆ EXPH.

## References

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