Hierarquia exponencial: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 17h11min de 14 de agosto de 2014

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:^[1]^[2]

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.

Referências

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

Links externos

Predefinição:CZoo

Predefinição:ComplexityClasses

[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.

[1]

[2]

@@ Linha 1: / Linha 1: @@
-Em [[teoria da complexidade computacional]], a '''hierarquia exponencial''' é a hierarquia da [[complexidade das classes]], que está em [[EXPTIME|tempo exponencial]], análogo a [[hierarquia polinomial]]. Como em outros lugares da teoria da complexidade, "exponencial" é usado em dois contextos diferentes (limite exponencial linear <math>2^{cn}</math> para uma constante ''c'', e limite exponencial completo <math>2^{n^c}</math>), levando a duas versões diferentes da hierarquia exponencial:<ref>Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in ''PH'', Theoretical Computer Science 158 (1996), no.&nbsp;1–2, pp.&nbsp;221–231.</ref><ref>Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no.&nbsp;1, pp.&nbsp;109–122.</ref>
+Em [[teoria da complexidade computacional]], a '''hierarquia exponencial''' é a hierarquia da [[complexidade das classes]], que pertencem à classe de [[EXPTIME|tempo exponencial]], análogo a [[hierarquia polinomial]]. Como em outros lugares da teoria da complexidade, "exponencial" é usado em dois contextos diferentes (limite exponencial linear <math>2^{cn}</math> para uma constante ''c'', e limite exponencial completo <math>2^{n^c}</math>), levando a duas versões diferentes da hierarquia exponencial:<ref>Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in ''PH'', Theoretical Computer Science 158 (1996), no.&nbsp;1–2, pp.&nbsp;221–231.</ref><ref>Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no.&nbsp;1, pp.&nbsp;109–122.</ref>
-*EH é a união das classes <math>\Sigma^E_k</math> para todo ''k,'' onde <math>\Sigma^E_k=\mathrm{NE}^{\Sigma^P_{k-1}}</math> (i.e, linguagens computáveis em tempo [[máquina de turing não deterministica|não determinístico]] <math>2^{cn}</math> para alguma constante ''c'' com <math>\Sigma^P_{k-1}</math> [[máquina de turing oracle|oracle]]. Uma outra definição  <math>\Pi^E_k=\mathrm{coNE}^{\Sigma^P_{k-1}}</math>, <math>\Delta^E_k=\mathrm E^{\Sigma^P_{k-1}}</math>. Uma definição equivalente é que a linguagem ''L'' está em <math>\Sigma^E_k</math> se e somente se ela pode ser escrita na forma
+*EH é a união das classes <math>\Sigma^E_k</math> para todo ''k,'' onde <math>\Sigma^E_k=\mathrm{NE}^{\Sigma^P_{k-1}}</math> (i.e, linguagens computáveis em tempo [[máquina de turing não deterministica|não determinístico]] <math>2^{cn}</math> para alguma constante ''c'' com oráculo  <math>\Sigma^P_{k-1}</math>. Uma outra definição  <math>\Pi^E_k=\mathrm{coNE}^{\Sigma^P_{k-1}}</math>, <math>\Delta^E_k=\mathrm E^{\Sigma^P_{k-1}}</math>. Uma definição equivalente é que a linguagem ''L'' está em <math>\Sigma^E_k</math> se e somente se ela pode ser escrita na forma
 ::<math>x\in L\iff\exists y_1\,\forall y_2\dots Qy_k\,R(x,y_1,\dots,y_k),</math>
 :onde <math>R(x,y_1,\dots,y_n)</math> é um predicado computável em tempo <math>2^{c|x|}</math> ( o que implicitamente limita o comprimento de ''y<sub>i</sub>''). Também equivalente, EH é a classe de linguagens computáveis em uma [[máquina de turing alternativa]] em tempo <math>2^{cn}</math> para algum ''c'' com constantes alterações.
-*EXPH é a união das classes <math>\Sigma^{EXP}_k</math>, onde <math>\Sigma^{EXP}_k=\mathrm{NEXP}^{\Sigma^P_{k-1}}</math> (linguagens computáveis em tempo não determinístico <math>2^{n^c}</math> para alguma constante ''c'' com <math>\Sigma^P_{k-1}</math> oracle), e novamente <math>\Pi^{EXP}_k=\mathrm{coNEXP}^{\Sigma^P_{k-1}}</math>, <math>\Delta^{EXP}_k=\mathrm{EXP}^{\Sigma^P_{k-1}}</math>. A linguagem ''L'' está em <math>\Sigma^{EXP}_k</math> se e somente se puder ser escrita na forma:
+*EXPH é a união das classes <math>\Sigma^{EXP}_k</math>, onde <math>\Sigma^{EXP}_k=\mathrm{NEXP}^{\Sigma^P_{k-1}}</math> (linguagens computáveis em tempo não determinístico <math>2^{n^c}</math> para alguma constante ''c'' com oráculo  <math>\Sigma^P_{k-1}</math>), e novamente <math>\Pi^{EXP}_k=\mathrm{coNEXP}^{\Sigma^P_{k-1}}</math>, <math>\Delta^{EXP}_k=\mathrm{EXP}^{\Sigma^P_{k-1}}</math>. A linguagem ''L'' está em <math>\Sigma^{EXP}_k</math> se e somente se puder ser escrita na forma:
 ::<math>x\in L\iff\exists y_1\,\forall y_2\dots Qy_k\,R(x,y_1,\dots,y_k),</math>
 :onde <math>R(x,y_1,\dots,y_k)</math> é computável em tempo <math>2^{n^c}</math> para algum ''c'', que novamente possui limites implícitos de comprimento ''y<sub>i</sub>''.