Hierarquia exponencial: diferenças entre revisões

Em [[teoria da complexidade computacional]], a '''hierarquia exponencial''' é a hierarquia da [[complexidade das classes]], que estápertencem emà 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 oráculo <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

*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> 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: