Hierarquia exponencial

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book-4.svg
Esta página ou secção cita fontes fiáveis e independentes, mas que não cobrem todo o conteúdo, o que compromete a verificabilidade (desde dezembro de 2015). Por favor, insira mais referências no texto. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde dezembro de 2015).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Translation to english arrow.svg
A tradução deste artigo está abaixo da qualidade média aceitável. É possível que tenha sido feita por um tradutor automático ou por alguém que não conhece bem o português ou a língua original do texto. Caso queira colaborar com a Wikipédia, tente encontrar a página original e melhore este verbete conforme o guia de tradução.

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