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 _{k}^{E}$ for all k, where $\Sigma _{k}^{E}=\mathrm {NE} ^{\Sigma _{k-1}^{P}}$ (i.e., languages computable in nondeterministic time $2^{cn}$ for some constant c with a $\Sigma _{k-1}^{P}$ oracle). One also defines $\Pi _{k}^{E}=\mathrm {coNE} ^{\Sigma _{k-1}^{P}}$, $\Delta _{k}^{E}=\mathrm {E} ^{\Sigma _{k-1}^{P}}$. An equivalent definition is that a language L is in $\Sigma _{k}^{E}$ 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 _{k}^{\mathrm {EXP} }$, where $\Sigma _{k}^{\mathrm {EXP} }=\mathrm {NEXP} ^{\Sigma _{k-1}^{P}}$ (languages computable in nondeterministic time $2^{n^{c}}$ for some constant c with a $\Sigma _{k-1}^{P}$ oracle), and again $\Pi _{k}^{\mathrm {EXP} }=\mathrm {coNEXP} ^{\Sigma _{k-1}^{P}}$, $\Delta _{k}^{\mathrm {EXP} }=\mathrm {EXP} ^{\Sigma _{k-1}^{P}}$. A language L is in $\Sigma _{k}^{\mathrm {EXP} }$ 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