Hierarquia exponencial

Em teoria da complexidade computacional, a hierarquia exponencial é a hierarquia da complexidade das classes, que pertencem à classe de tempo exponencial, análogo a hierarquia polinomial. Como em outros lugares da teoria da complexidade, "exponencial" é usado em dois contextos diferentes (limite exponencial linear $2^{cn}$ para uma constante c, e limite exponencial completo $2^{n^{c}}$), levando a duas versões diferentes da hierarquia exponencial:

• EH é a união das classes $\Sigma _{k}^{E}$ para todo k, onde $\Sigma _{k}^{E}=\mathrm {NE} ^{\Sigma _{k-1}^{P}}$ (i.e, linguagens computáveis em tempo não determinístico $2^{cn}$ para alguma constante c com oráculo $\Sigma _{k-1}^{P}$. Uma outra definição $\Pi _{k}^{E}=\mathrm {coNE} ^{\Sigma _{k-1}^{P}}$, $\Delta _{k}^{E}=\mathrm {E} ^{\Sigma _{k-1}^{P}}$. Uma definição equivalente é que a linguagem L está em $\Sigma _{k}^{E}$ se e somente se ela pode ser escrita na forma

$x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{k}\,R(x,y_{1},\dots ,y_{k}),$

onde $R(x,y_{1},\dots ,y_{n})$ é um predicado computável em tempo $2^{c|x|}$ ( o que implicitamente limita o comprimento de y_i). Também equivalente, EH é a classe de linguagens computáveis em uma máquina de turing alternativa em tempo $2^{cn}$ para algum c com constantes alterações.

• EXPH é a união das classes $\Sigma _{k}^{EXP}$, onde $\Sigma _{k}^{EXP}=\mathrm {NEXP} ^{\Sigma _{k-1}^{P}}$ (linguagens computáveis em tempo não determinístico $2^{n^{c}}$ para alguma constante c com oráculo $\Sigma _{k-1}^{P}$), e novamente $\Pi _{k}^{EXP}=\mathrm {coNEXP} ^{\Sigma _{k-1}^{P}}$, $\Delta _{k}^{EXP}=\mathrm {EXP} ^{\Sigma _{k-1}^{P}}$. A linguagem L está em $\Sigma _{k}^{EXP}$ se e somente se puder ser escrita na forma:

$x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{k}\,R(x,y_{1},\dots ,y_{k}),$

onde $R(x,y_{1},\dots ,y_{k})$ é computável em tempo $2^{n^{c}}$ para algum c, que novamente possui limites implícitos de comprimento y_i.

Equivalentemente, EXPH é a classe de linguagens computáveis em tempo $2^{n^{c}}$ em uma máquina de turing alternante com constantes alternâncias. Temos E ⊆ NE ⊆ EH ⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, and EH ⊆ EXPH.