# 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

EH is the union of the classes $\Sigma _{k}^{\mathsf {E}}$  for all k, where $\Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}$  (i.e., languages computable in nondeterministic time $2^{cn}$  for some constant c with a $\Sigma _{k-1}^{\mathsf {P}}$  oracle). One also defines

$\Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.$

An equivalent definition is that a language L is in $\Sigma _{k}^{\mathsf {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},\ldots ,y_{k}),$

where $R(x,y_{1},\ldots ,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

EXPH is the union of the classes $\Sigma _{k}^{\mathsf {EXP}}$ , where $\Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}$  (languages computable in nondeterministic time $2^{n^{c}}$  for some constant c with a $\Sigma _{k-1}^{\mathsf {P}}$  oracle), and again:

$\Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.$

A language L is in $\Sigma _{k}^{\mathsf {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},\ldots ,y_{k}),$

where $R(x,y_{1},\ldots ,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.

## Comparison

ENE ⊆ EH ⊆ ESPACE,
EXPNEXP ⊆ EXPH ⊆ EXPSPACE,
EH ⊆ EXPH.