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:

• 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.

External links

Complexity Zoo: Class EH