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.

Referências

Ligações externas

Predefinição:CZoo