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.

Referências

1. Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in PH, Theoretical Computer Science 158 (1996), no. 1–2, pp. 221–231.
2. Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.

Ligações externas

Predefinição:CZoo