P/polinomial

Na Teoria da complexidade computacional, P/poly é a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma máquina de Turing com um polynomial-bounded advice function. É também equivalentemente definida como a classe PSIZE de linguagens que possuem um circuito de tamanho polinomial. Isso significa que a máquina que reconhece uma linguagem pode usar uma função de aconselhamento diferente ou usar um circuito diferente dependendo do tamanho da entrada,e que a função de aconselhamento ou circuito irá variar apenas em função do tamanho da entrada.

Por exemplo, o popular teste de primalidade Miller-Rabin pode ser formulado como um algoritmo P/polinomial: o "conselho" é uma lista de candidatos de valores para serem testados. É possível pré-computar uma lista de, no máximo, N valores de tal forma que todos os números de n-bits vão ter a certeza de ter uma testemunha a na lista. Por exemplo, se estamos testando um número de 32 bits, é suficiente para testar a = 2, 7 e 61. isso decorre do fato de que para cada n composto, 3/4s de todos os possíveis valores de A são testemunhas; um argumento de contagem simples, semelhante ao da prova de que BPP em P/polinomial abaixo mostra que não existe uma lista adequada de valores para A para cada tamanho de entrada, apesar que encontrá-lo pode ser caro.

Note que P/polinomial, ao contrário de outras classes de tempo polinomial, como P ou BPP, não é geralmente considerada uma classe de computação prática. Na verdade, isso contém todas as linguagens unárias "indecidíveis", nenhuma das quais pode ser resolvido geralmente por computadores reais. Por outro lado, se o comprimento de entrada é delimitada por um número relativamente pequeno, e as strings de aconselhamento são curtas, isso pode ser usado para modelar algoritmos práticos, com uma fase cara de pré-processamento separadamente de uma fase de processamento rápido, tal como no exemplo acima.

Importância do P/polinomial

P/polinomial é uma classe importante por muitas razões. Para ciência da computação teórica, há várias propriedades importantes que dependem de P/polinomial:

• Se NP ⊆ P/polinomial então PH (a hierarquia polinomial) cai para ${\mathrm{\Sigma }}_2^{\mathrm{P}}$. Este resultado é o teorema de Karp-Lipton. Além disso, NP ⊆ P/polinomial implica em AM = MA

• Se PSPACE'⊆ P/polinomialentãoPSPACE = ${\mathrm{\Sigma }}_2^{\mathrm{P}}\cap {\mathrm{\Pi }}_2^{\mathrm{P}}$, mesmo PSPACE = MA'.

Prova: Considere uma linguagem L de PSPACE. Sabe-se que existe uma sistema interactivo de prova para L, em que as ações do provador pode ser realizada por uma máquina PSPACE. Por hipótese, o provador pode ser substituído por um circuito de tamanho polinomial. Portanto, L tem um protocolo MA: Merlin envia o circuito como prova; e Arthur pode simular um protocolo IP ele mesmo, sem qualquer ajuda adicional.

• Se P ^#P ⊆ P/polinomial então P^#P = MA. A prova é semelhante à anterior, com base em um protocolo interativo para permanente e #P-completude de permanente.

• Se EXPTIME ⊆ P/polinomial então EXPTIME = ${\mathrm{\Sigma }}_2^{\mathrm{P}}\cap {\mathrm{\Pi }}_2^{\mathrm{P}}$ (Teorema de Meyer), inclusive EXPTIME = MA.
• Se NEXPTIME ⊆ P/polinomial então NEXPTIME = EXPTIME, inclusive NEXPTIME = MA. Reciprocamente, NEXPTIME = MA implica NEXPTIME ⊆ P/polinomial.
• Se EXP^NP ⊆ P/polinomial então EXP^NP = ${\mathrm{\Sigma }}_2^{\mathrm{P}}\cap {\mathrm{\Pi }}_2^{\mathrm{P}}$ (Buhrman, Homer).
• É sabido que MA_EXP, uma versão exponencial do MA, não está contido em P/polinomial.

Prova: Se MA_EXP ⊆ P/polinomial então PSPACE = MA (veja acima). Por padding, EXPSPACE = MA_EXP, portanto EXPSPACE ⊆ P/polinomial, mas isso pode ser provado como falso através da diagonalização.

Uma das razões mais interessantes pela qual P/poli é importante é a propriedade que, se NP não é um subconjunto de P/polinomal, então P ≠ NP. Esta observação foi o centro de muitas tentativas de provar que P ≠ NP.

P/polinomial é também utilizado no campo da criptografia. A segurança é geralmente definida "contra" adversários de P/ polinomial. Além de incluir os modelos mais práticos de computação, como o BPP, este admite também a possibilidade de que adversários podem fazer pré-computações pesadas, para entradas de até um determinado comprimento, como na construção de tabelas Arco-Íris.

Embora nem todas as linguagens em P/polinomial sejam linguagens esparsas, existe uma redução em tempo polinomial a uma máquina de Turing a partir de qualquer linguagem em P/polinomial a um linguagem esparsa.

Teorema de Adleman

O Teorema de Adleman, provado por Leonard Adleman, afirma que BPP ⊆ P/polinomial, onde BPP é o conjunto de problemas que podem ser resolvidos com algoritmos aleatórios com erro de dois lados em tempo polinomial.

Variantes do teorema mostram que BPL está contido em L/polinomial e AM está contido em NP/polinomial.

Prova

Seja L uma linguagem em BPP, e seja M(x,r) um algoritmo de tempo polinomial que decide L com o erro ≤ 1/3 (onde x é a string de entrada e r é um conjunto de bits aleatórios).

Construir uma nova máquina MPredefinição:'(x,R), que roda M 18n vezes (onde n é o comprimento de entrada e R é uma sequência de 18n independentemente aleatória rs). Assim, MPredefinição:' também executa em tempo polinomial; e tem uma probabilidade de erro ≤ 1/e ⁿ por Chernoff bound. Se conseguirmos corrigir R, então, obtém-se um algoritmo que é determinístico.

Se Bad(x) é definido por {R: MPredefinição:'(x,R) é incorreto}, então temos:

$\mathrm{\forall }x{\text{Prob}}_R[R\in \text{Bad}(x)]\le \frac{1}{e^n}.$

O tamanho da entrada é n, por isso existem 2ⁿ possíveis entradas. Assim, a probabilidade de que um R aleatório é mau para pelo menos uma entrada x é:

${\text{Prob}}_R[\mathrm{\exists }xR\in \text{Bad}(x)]\le \frac{2^n}{e^n}<1.$

Em outras palavras, a probabilidade de que R é mau para algum x é inferior a 1, por isso deve haver um R que é bom para todo x. Usa-se um R para ser a string de aconselhamento no algoritmo P/polinomial.

Veja também

• Lista de algoritmos