# 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 yi). 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 yi. Equivalently, EXPH is the class of languages computable in time $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.