Hierarquia polinomial
Este artigo não cita fontes confiáveis. (Dezembro de 2011) |
No ramo da Complexidade computacional a hierarquia polinomial é a hierarquia das Classes de complexidade que generaliza as classes P, NP e Co-NP para Máquinas oráculo. É uma contrapartida limitada de recursos para a Hierarquia aritmética e Hierarquia analítica da Lógica matemática.
Definições
[editar | editar código-fonte]Existem várias definições equivalentes para as classes de hierarquia polinomial.
1. Para a definição do oráculo da hierarquia polinomial, defina:
:
onde P é o conjunto de problemas de decisão que podem ser resolvidos em tempo polinomial. Então, para i ≥ 0 defina:
: : :
tal que AB é o conjunto de problemas de decisão solucionável por uma maquina de Turing na classe A aumentada por um oráculo para um problema completo na classe B. Por exemplo, </math>, and é a classe de problemas solucionáveis em tempo polinomial por um oráculo para um dado problema NP-Completo.
2. Para a definição existencial/universal da definição de hierarquia polinomial, assuma que seja uma linguagem ( i.e. um problema de decisão, como o sub-conjunto de {0,1}* ), seja um polinômio e defina:
:
Tal que é algum padrão de codificação para o par de strings binárias x e y como uma única string binária. L representa o conjunto de pares ordenados de strings, onde a primeira string x é um membro de e a segunda string w sendo "short" ( ) que diz que x é membro de . Em outras palavras, se e somente se existe uma testemunha w "short" tal que . Da mesma forma, define:
:
Note que osteoremas de De Morgan permanecem válidos. e , onde Lc é o complemento de L.
Considere como a classe das linguagens. Extenda esses operadores para trabalhar em classes inteiras de linguagens pela definição:
: :
Novamente, os teoremas de De Morgan permanece válidos. e , onde .
As classes NP e Co-NP podem ser definidas como e , onde P é a classe de todas as linguagens decidíveis viáveis ( Tempo polinomial ). A hierarquia polinomial pode ser definida recursivamente como:
: : :
Note que e .
Essa definição reflete a conexão forte entre hierarquia polinomial e a Hierarquia aritmética, onde R e RE são análogas a P e NP, respectivamente. A Hierarquia analítica também é definida de forma parecida para dar hierarquia para sub-conjuntos dos números reais.
3. Uma definição equivalente em termos de uma Máquina de Turing alternada define ( respectivamente, ) como o conjunto de problemas de decisão solvíveis em tempo polinomial em uma máquina de Turing alternada com alternações, iniciando em um estado inicial.
Relações entre as classes na hierarquia polinomial
[editar | editar código-fonte]![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Polynomial_time_hierarchy.svg/250px-Polynomial_time_hierarchy.svg.png)
As definições implicam nas relações:
Diferentemente das hierarquias aritimétrica e analitica, as quais tem inclusões certas, é uma questão aberta se qualquer uma dessas inclusões é certa, embora acredita-se que elas sejam todas verdade. Se qualquer ou , então a hierarquia desmorona para o nível k: Para todo , . Em particular, se P = NP a hierarquia desmorona completamente.
A união de todas as classes na hierarquia polinomial tem como complexidade a classe PH.
Propriedades
[editar | editar código-fonte]A hierarquia polinomial é análoga ( em uma complexidade bem menor )a Hierarquia exponencial e Hierarquia aritmética.
Sabemos que PH está contido em PSPACE, mas não se sabe se as duas classes são iguais. Uma reformulação útil desse problema é que PH = PSPACE se e somente se estruturas de lógica de segunda ordem não ganham nenhuma força da adição da operação Fechamento sobre transitividade.
Se a hierarquia polinomial possuir algum problema completo, então ela possui um número finito de niveis. Já que temos PSPACE-completude problemas, sabemos que se PSPACE = PH, então a hierarquia polinomial irá desmoronar, uma vez que se um problema completo de PSPACE seria -completo para algum k.
Cada classe na hierarquia polinomial contem problemas -completo ( Problemas completo sobre um tempo polinomial de redução muitos para um ). Além do mais, cada classe na hierarquia polinomial é fechada sob -reduções: Signifcando que para a classe na hierarquia e uma linguagem , se então também. Juntos, esses dois fatos implicam em que se é um problema completo para , então e . Em outras palavras, se uma linguagem é definida em algum oráculo em , então podemos assumir que é definido baseado em um problema completo para . Problemas completos então atuam como "representantes" das classes para as quais eles são completos.
O Teorema de Sipser–Lautemann afirma que a classe BPP está contida em um segundo nível da hierarquia polinomial.
O Teorema de Karp–Lipton afirma que para qualquer k, não está contido em SIZE(nk).
O Teorema de Toda afirma que a hierarquia polinomial está contida em P#P.
Problemas na hierarquia polinomial
[editar | editar código-fonte]Um exemplo de um problema natural em é a minimização de circuitos. Dado um número k e um circuito A computando uma Função booleana f, determina se existe um circuito com pelo menos K chaves que computa a mesma função f. Seja o conjunto de todos os circuitos booleanos, a linguagem:
É dicidivel em tempo polinomial. A linguagem:
É a linguagem de minimização de circuitos. pois é decidivel em tempo polinomial e porque, dados , se e somente se existe um circuito tal que para todas as entradas , .
Um problema completo para é a satisfatibilidade para formulas booleanas com k alterações de quantificadores ( Abreviando, QBFk ou QSATk ). Essa é a versão do Problema de satisfatibilidade booliana para . Nesse problema, nos recebemos uma formula booleana f com variaveis particionadas em k conjuntos, X1, ..., Xk. Temos que determinar a veracidade de:
Isso é, existe uma valoração para as variáveis em X1 tal que, para todas as valorações em X2, existe uma valoração de valores para as variaveis em X3, ... f é verdade? A variação do problema acima é completa para . A variante na qual o primeiro quantificador é para todos, o segundo Existe', etc., é completa para .
Ver também
[editar | editar código-fonte]Bibliografia
[editar | editar código-fonte]- A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pp. 125–129, 1972. O artigo que introduziu hierarquia polinomial.
- L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, vol.3, pp. 1–22, 1976.
- C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. Polynomial hierarchy, pp. 409–438.
- Michael R. Garey and David S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness. Section 7.2: The Polynomial Hierarchy, pp. 161–167.