# 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

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$_1$, ..., 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$_1$ tal que, para todas as valorações em X$_2$, existe uma valoração de valores para as variaveis em X$_3$, ... 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}}$.