Hierarquia polinomial

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:

:$\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:

:$\Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}$ :$\Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}$ :$\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 $\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$ seja uma linguagem ( i.e. um problema de decisão, como o sub-conjunto de {0,1}* ), seja $P$ um polinômio e defina:

: $\exists ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},$

Tal que $\langle x,w\rangle \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 $\exists ^{p}L$ e a segunda string w sendo "short" ( $|w|\leq p(|x|)$ ) que diz que x é membro de $\exists ^{p}L$. Em outras palavras, $x\in \exists ^{p}L$ se e somente se existe uma testemunha w "short" tal que $\langle x,w\rangle inL$. Da mesma forma, define:

: $\forall ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}$

Note que osteoremas de De Morgan permanecem válidos. $\left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}$ e $\left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}$, onde L^c é o complemento de L.

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

:$\exists ^{\rm {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\mbox{ é polinomial e }}L\in {\mathcal {C}}\right\}$ :$\forall ^{\rm {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\mbox{ é polinomial e }}L\in {\mathcal {C}}\right\}$

Novamente, os teoremas de De Morgan permanece válidos. ${\rm {co}}\exists ^{\rm {P}}{\mathcal {C}}=\forall ^{\rm {P}}{\rm {co}}{\mathcal {C}}$ e ${\rm {co}}\forall ^{\rm {P}}{\mathcal {C}}=\exists ^{\rm {P}}{\rm {co}}{\mathcal {C}}$, onde ${\rm {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}$.

As classes NP e Co-NP podem ser definidas como ${\rm {NP}}=\exists ^{\rm {P}}{\rm {P}}$ e ${\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:

:$\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\rm {P}}$ :$\Sigma _{k+1}^{\rm {P}}:=\exists ^{\rm {P}}\Pi _{k}^{\rm {P}}$ :$\Pi _{k+1}^{\rm {P}}:=\forall ^{\rm {P}}\Sigma _{k}^{\rm {P}}$

Note que ${\rm {NP}}=\Sigma _{1}^{\rm {P}}$ e ${\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 $\Sigma _{k}^{\rm {P}}$ ( respectivamente, $\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$ 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:

$\Sigma _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Sigma _{i+1}^{\rm {P}}$

$\Pi _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Pi _{i+1}^{\rm {P}}$

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

Cada classe na hierarquia polinomial contem problemas $\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 $\leq _{\rm {m}}^{\rm {P}}$-reduções: Signifcando que para a classe ${\mathcal {C}}$ na hierarquia e uma linguagem $L\in {\mathcal {C}}$, se $A\leq _{\rm {m}}^{\rm {P}}L$ então $A\in {\mathcal {C}}$ também. Juntos, esses dois fatos implicam em que se $K_{i}$ é um problema completo para $\Sigma _{i}^{\rm {P}}$, então $\Sigma _{i+1}^{\rm {P}}=\left(\Sigma _{i}^{\rm {P}}\right)^{K_{i}}$ e $\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 ${\mathcal {C}}$, então podemos assumir que é definido baseado em um problema completo para ${\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, $\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 $\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 ${\mathcal {C}}$ o conjunto de todos os circuitos booleanos, a linguagem:

$L=\left\{\langle A,k,B,x\rangle \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:

${\mathit {CM}}=\left\{\langle A,k\rangle \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. ${\mathit {CM}}\in \Sigma _{2}^{P}(=\exists ^{\rm {P}}\forall ^{\rm {P}}{\rm {P}})$ pois ${\mathcal {L}}$ é decidivel em tempo polinomial e porque, dados $\langle A,k\rangle$, $\langle A,k\rangle \in {\mathit {CM}}$ se e somente se existe um circuito ${\mathcal {B}}$ tal que para todas as entradas $x$, $\langle A,k,B,x\rangle \in L$.

Um problema completo para $\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 $\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:

$\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 $\Sigma _{k}^{\rm {P}}$. A variante na qual o primeiro quantificador é para todos, o segundo Existe', etc., é completa para $\Pi _{k}^{\rm {P}}$.

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