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 ${\displaystyle 2^{cn}}$ para uma constante c, e limite exponencial completo ${\displaystyle 2^{n^{c}}}$), levando a duas versões diferentes da hierarquia exponencial:^[1][2]

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

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

onde ${\displaystyle R(x,y_{1},\dots ,y_{n})}$ é um predicado computável em tempo ${\displaystyle 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 ${\displaystyle 2^{cn}}$ para algum c com constantes alterações.

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

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

onde ${\displaystyle R(x,y_{1},\dots ,y_{k})}$ é computável em tempo ${\displaystyle 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 ${\displaystyle 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.