Hierarquia exponencial

Predefinição:Mais notas Predefinição:Reciclagem Predefinição:Má tradução 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 ${\mathrm{\Sigma }}_k^E$ para todo k, onde ${\mathrm{\Sigma }}_k^E={\mathrm{N}\mathrm{E}}^{{\mathrm{\Sigma }}_{k-1}^P}$ (i.e, linguagens computáveis em tempo não determinístico $2^{cn}$ para alguma constante c com oráculo ${\mathrm{\Sigma }}_{k-1}^P$. Uma outra definição ${\mathrm{\Pi }}_k^E={\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{E}}^{{\mathrm{\Sigma }}_{k-1}^P}$, ${\mathrm{\Delta }}_k^E={\mathrm{E}}^{{\mathrm{\Sigma }}_{k-1}^P}$. Uma definição equivalente é que a linguagem L está em ${\mathrm{\Sigma }}_k^E$ se e somente se ela pode ser escrita na forma

$x\in L⟺\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\dots Q{y}_{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 ${\mathrm{\Sigma }}_k^{EXP}$, onde ${\mathrm{\Sigma }}_k^{EXP}={\mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}}^{{\mathrm{\Sigma }}_{k-1}^P}$ (linguagens computáveis em tempo não determinístico $2^{n^c}$ para alguma constante c com oráculo ${\mathrm{\Sigma }}_{k-1}^P$), e novamente ${\mathrm{\Pi }}_k^{EXP}={\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}}^{{\mathrm{\Sigma }}_{k-1}^P}$, ${\mathrm{\Delta }}_k^{EXP}={\mathrm{E}\mathrm{X}\mathrm{P}}^{{\mathrm{\Sigma }}_{k-1}^P}$. A linguagem L está em ${\mathrm{\Sigma }}_k^{EXP}$ se e somente se puder ser escrita na forma:

$x\in L⟺\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\dots Q{y}_{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.