Btukfyl

Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde dezembro de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido. —Encontre fontes: Google (notícias, livros e acadêmico)

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 |

Existem várias definições equivalentes para as classes de hierarquia polinomial.

1. Para a definição do oráculo da hierarquia polinomial, defina:

:Δ0P:=Σ0P:=Π0P:=P,{displaystyle Delta _{0}^{rm {P}}:=Sigma _{0}^{rm {P}}:=Pi _{0}^{rm {P}}:={mbox{P}},}

onde P é o conjunto de problemas de decisão que podem ser resolvidos em tempo polinomial. Então, para i ≥ 0 defina:

:Δi+1P:=PΣiP{displaystyle Delta _{i+1}^{rm {P}}:={mbox{P}}^{Sigma _{i}^{rm {P}}}}
:Σi+1P:=NPΣiP{displaystyle Sigma _{i+1}^{rm {P}}:={mbox{NP}}^{Sigma _{i}^{rm {P}}}}
:Πi+1P:=coNPΣiP{displaystyle Pi _{i+1}^{rm {P}}:={mbox{coNP}}^{Sigma _{i}^{rm {P}}}}

tal que A^B é 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 Δ2P=PNP{displaystyle Delta _{2}^{rm {P}}={rm {P^{NP}}}} é 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 L{displaystyle L} seja uma linguagem ( i.e. um problema de decisão, como o sub-conjunto de {0,1}* ), seja P{displaystyle P} um polinômio e defina:

: ∃pL:={x∈{0,1}∗ | (∃w∈{0,1}≤p(|x|))⟨x,w⟩∈L},{displaystyle exists ^{p}L:=left{xin {0,1}^{*} left| left(exists win {0,1}^{leq p(|x|)}right)langle x,wrangle in Lright.right},}

Tal que ⟨x,w⟩∈{0,1}∗{displaystyle langle x,wrangle in {0,1}^{*}} é 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 ∃pL{displaystyle exists ^{p}L} e a segunda string w sendo "short" ( |w|≤p(|x|){displaystyle |w|leq p(|x|)} ) que diz que x é membro de ∃pL{displaystyle exists ^{p}L}. Em outras palavras, x∈∃pL{displaystyle xin exists ^{p}L} se e somente se existe uma testemunha w "short" tal que ⟨x,w⟩inL{displaystyle langle x,wrangle inL}. Da mesma forma, define:

: ∀pL:={x∈{0,1}∗ | (∀w∈{0,1}≤p(|x|))⟨x,w⟩∈L}{displaystyle forall ^{p}L:=left{xin {0,1}^{*} left| left(forall win {0,1}^{leq p(|x|)}right)langle x,wrangle in Lright.right}}

Note que osteoremas de De Morgan permanecem válidos. (∃pL)c=∀pLc{displaystyle left(exists ^{p}Lright)^{rm {c}}=forall ^{p}L^{rm {c}}} e (∀pL)c=∃pLc{displaystyle left(forall ^{p}Lright)^{rm {c}}=exists ^{p}L^{rm {c}}}, onde L^c é o complemento de L.

Considere C{displaystyle {mathcal {C}}} como a classe das linguagens. Extenda esses operadores para trabalhar em classes inteiras de linguagens pela definição:

:∃PC:={∃pL | p é polinomial e L∈C}{displaystyle exists ^{rm {P}}{mathcal {C}}:=left{exists ^{p}L | p{mbox{ é polinomial e }}Lin {mathcal {C}}right}}
:∀PC:={∀pL | p é polinomial e L∈C}{displaystyle forall ^{rm {P}}{mathcal {C}}:=left{forall ^{p}L | p{mbox{ é polinomial e }}Lin {mathcal {C}}right}}

Novamente, os teoremas de De Morgan permanece válidos. co∃PC=∀PcoC{displaystyle {rm {co}}exists ^{rm {P}}{mathcal {C}}=forall ^{rm {P}}{rm {co}}{mathcal {C}}} e co∀PC=∃PcoC{displaystyle {rm {co}}forall ^{rm {P}}{mathcal {C}}=exists ^{rm {P}}{rm {co}}{mathcal {C}}}, onde coC={Lc|L∈C}{displaystyle {rm {co}}{mathcal {C}}=left{L^{c}|Lin {mathcal {C}}right}}.

As classes NP e Co-NP podem ser definidas como NP=∃PP{displaystyle {rm {NP}}=exists ^{rm {P}}{rm {P}}} e
coNP=∀PP{displaystyle {rm {coNP}}=forall ^{rm {P}}{rm {P}}}, onde P é a classe de todas as linguagens decidíveis viáveis ( Tempo polinomial ). A hierarquia polinomial pode ser definida recursivamente como:

:Σ0P:=Π0P:=P{displaystyle Sigma _{0}^{rm {P}}:=Pi _{0}^{rm {P}}:={rm {P}}}
:Σk+1P:=∃PΠkP{displaystyle Sigma _{k+1}^{rm {P}}:=exists ^{rm {P}}Pi _{k}^{rm {P}}}
:Πk+1P:=∀PΣkP{displaystyle Pi _{k+1}^{rm {P}}:=forall ^{rm {P}}Sigma _{k}^{rm {P}}}

Note que NP=Σ1P{displaystyle {rm {NP}}=Sigma _{1}^{rm {P}}} e coNP=Π1P{displaystyle {rm {coNP}}=Pi _{1}^{rm {P}}}.

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 ΣkP{displaystyle Sigma _{k}^{rm {P}}} ( respectivamente, ΠkP{displaystyle Pi _{k}^{rm {P}}} ) como o conjunto de problemas de decisão solvíveis em tempo polinomial em uma máquina de Turing alternada com K{displaystyle K} alternações, iniciando em um estado inicial.

Relações entre as classes na hierarquia polinomial |

Representação pictorial da hierarquia polinomial. As setas denotam inclusão.

As definições implicam nas relações:

ΣiP⊆Δi+1P⊆Σi+1P{displaystyle Sigma _{i}^{rm {P}}subseteq Delta _{i+1}^{rm {P}}subseteq Sigma _{i+1}^{rm {P}}}

ΠiP⊆Δi+1P⊆Πi+1P{displaystyle Pi _{i}^{rm {P}}subseteq Delta _{i+1}^{rm {P}}subseteq Pi _{i+1}^{rm {P}}}

ΣiP=coΠiP{displaystyle Sigma _{i}^{rm {P}}={rm {co}}Pi _{i}^{rm {P}}}

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 ΣkP=Σk+1P{displaystyle Sigma _{k}^{rm {P}}=Sigma _{k+1}^{rm {P}}} ou ΣkP=ΠkP{displaystyle Sigma _{k}^{rm {P}}=Pi _{k}^{rm {P}}}, então a hierarquia desmorona para o nível k: Para todo i>k{displaystyle i>k}, ΣiP=ΣkP{displaystyle Sigma _{i}^{rm {P}}=Sigma _{k}^{rm {P}}}. 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 |

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 ΣkP{displaystyle Sigma _{k}^{rm {P}}}-completo para algum k.

Cada classe na hierarquia polinomial contem problemas ≤mP{displaystyle leq _{rm {m}}^{rm {P}}}-completo ( Problemas completo sobre um tempo polinomial de redução muitos para um ). Além do mais, cada classe na hierarquia polinomial é fechada sob ≤mP{displaystyle leq _{rm {m}}^{rm {P}}}-reduções: Signifcando que para a classe C{displaystyle {mathcal {C}}} na hierarquia e uma linguagem L∈C{displaystyle Lin {mathcal {C}}}, se A≤mPL{displaystyle Aleq _{rm {m}}^{rm {P}}L} então A∈C{displaystyle Ain {mathcal {C}}} também. Juntos, esses dois fatos implicam em que se Ki{displaystyle K_{i}} é um problema completo para ΣiP{displaystyle Sigma _{i}^{rm {P}}}, então Σi+1P=(ΣiP)Ki{displaystyle Sigma _{i+1}^{rm {P}}=left(Sigma _{i}^{rm {P}}right)^{K_{i}}} e Πi+1P=(ΠiP)Kic{displaystyle Pi _{i+1}^{rm {P}}=left(Pi _{i}^{rm {P}}right)^{K_{i}^{rm {c}}}}. Em outras palavras, se uma linguagem é definida em algum oráculo em C{displaystyle {mathcal {C}}}, então podemos assumir que é definido baseado em um problema completo para C{displaystyle {mathcal {C}}}. 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, Σ2{displaystyle Sigma _{2}} não está contido em SIZE(n^k).

O Teorema de Toda afirma que a hierarquia polinomial está contida em P^#P.

Problemas na hierarquia polinomial |

Um exemplo de um problema natural em Σ2P{displaystyle Sigma _{2}^{rm {P}}} é 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 C{displaystyle {mathcal {C}}} o conjunto de todos os circuitos booleanos, a linguagem:

L={⟨A,k,B,x⟩∈C×N×C×{0,1}∗|B tem no máximo k chaves, e A(x)=B(x)}{displaystyle L=left{langle A,k,B,xrangle in {mathcal {C}}times mathbb {N} times {mathcal {C}}times {0,1}^{*}left|B{mbox{ tem no máximo }}k{mbox{ chaves, e }}A(x)=B(x)right.right}}

É dicidivel em tempo polinomial. A linguagem:

CM={⟨A,k⟩∈C×N|existe um circuito B com no máximo k chaves  tal que A e B computam a mesma função }{displaystyle {mathit {CM}}=left{langle A,krangle in {mathcal {C}}times mathbb {N} left|{begin{matrix}{mbox{existe um circuito }}B{mbox{ com no máximo }}k{mbox{ chaves }}\{mbox{ tal que }}A{mbox{ e }}B{mbox{ computam a mesma função }}end{matrix}}right.right}}

É a linguagem de minimização de circuitos. CM∈Σ2P(=∃P∀PP){displaystyle {mathit {CM}}in Sigma _{2}^{P}(=exists ^{rm {P}}forall ^{rm {P}}{rm {P}})} pois L{displaystyle {mathcal {L}}} é decidivel em tempo polinomial e porque, dados ⟨A,k⟩{displaystyle langle A,krangle }, ⟨A,k⟩∈CM{displaystyle langle A,krangle in {mathit {CM}}} se e somente se existe um circuito B{displaystyle {mathcal {B}}} tal que para todas as entradas x{displaystyle x}, ⟨A,k,B,x⟩∈L{displaystyle langle A,k,B,xrangle in L}.

Um problema completo para ΣkP{displaystyle Sigma _{k}^{rm {P}}} é a satisfatibilidade para formulas booleanas com k alterações de quantificadores ( Abreviando, QBF_k ou QSAT_k ). Essa é a versão do Problema de satisfatibilidade booliana para ΣkP{displaystyle Sigma _{k}^{rm {P}}}. Nesse problema, nos recebemos uma formula booleana f com variaveis particionadas em k conjuntos, X₁, ..., X_k. Temos que determinar a veracidade de:

∃X1∀X2∃X3…f{displaystyle exists X_{1}forall X_{2}exists X_{3}ldots f}

Isso é, existe uma valoração para as variáveis em X₁ tal que, para todas as valorações em X₂, existe uma valoração de valores para as variaveis em X₃, ... f é verdade? A variação do problema acima é completa para ΣkP{displaystyle Sigma _{k}^{rm {P}}}. A variante na qual o primeiro quantificador é para todos, o segundo Existe', etc., é completa para ΠkP{displaystyle Pi _{k}^{rm {P}}}.

Veja Também |

Exptime

Bibliografia |

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