Exponential hierarchy

EXPH

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

${\displaystyle {\mathrm{\Pi }}_k^{\mathsf{E}\mathsf{X}\mathsf{P}}={\mathsf{c}\mathsf{o}\mathsf{N}\mathsf{E}\mathsf{X}\mathsf{P}}^{{\mathrm{\Sigma }}_{k-1}^{\mathsf{P}}},{\mathrm{\Delta }}_k^{\mathsf{E}\mathsf{X}\mathsf{P}}={\mathsf{E}\mathsf{X}\mathsf{P}}^{{\mathrm{\Sigma }}_{k-1}^{\mathsf{P}}}.}$

A language L is in ${\displaystyle {\mathrm{\Sigma }}_k^{\mathsf{E}\mathsf{X}\mathsf{P}}}$ if and only if it can be written as

${\displaystyle x\in L⟺\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\dots Q{y}_{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 y_i. Equivalently, EXPH is the class of languages computable in time ${\displaystyle 2^{n^c}}$ on an alternating Turing machine with constantly many alternations.

Comparison

E ⊆ NE ⊆ EH⊆ ESPACE,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE,

EH ⊆ EXPH.