Hierarquia exponencial

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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 para uma constante c, e limite exponencial completo ), levando a duas versões diferentes da hierarquia exponencial:[1][2]

  • EH é a união das classes para todo k, onde (i.e, linguagens computáveis em tempo não determinístico para alguma constante c com oráculo . Uma outra definição , . Uma definição equivalente é que a linguagem L está em se e somente se ela pode ser escrita na forma
onde é um predicado computável em tempo ( o que implicitamente limita o comprimento de yi). Também equivalente, EH é a classe de linguagens computáveis em uma máquina de turing alternativa em tempo para algum c com constantes alterações.
  • EXPH é a união das classes , onde (linguagens computáveis em tempo não determinístico para alguma constante c com oráculo ), e novamente , . A linguagem L está em se e somente se puder ser escrita na forma:
onde é computável em tempo para algum c, que novamente possui limites implícitos de comprimento yi.

Equivalentemente, EXPH é a classe de linguagens computáveis em tempo em uma máquina de turing alternante com constantes alternâncias. Temos ENE ⊆ EH ⊆ ESPACE, EXPNEXP ⊆ 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[editar | editar código-fonte]

Predefinição:CZoo