PROFILPELAJAR.COM

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.^[1]^[2] 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.^[3] 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 $\Sigma _{2}^{\rm {P}}$ . Este resultado é o teorema de Karp-Lipton. Além disso, NP ⊆ P/polinomial implica em AM = MA^[4]

Se PSPACE'⊆ P/polinomialentãoPSPACE = $\Sigma _{2}^{\rm {P}}\cap \Pi _{2}^{\rm {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.^[5] A prova é semelhante à anterior, com base em um protocolo interativo para permanente e #P-completude de permanente.

Se EXPTIME ⊆ P/polinomial então EXPTIME = $\Sigma _{2}^{\rm {P}}\cap \Pi _{2}^{\rm {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.^[6]
Se EXP^NP ⊆ P/polinomial então EXP^NP = $\Sigma _{2}^{\rm {P}}\cap \Pi _{2}^{\rm {P}}$ (Buhrman, Homer).^[7]
É 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.^[8]

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.^[9]

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 M'(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, M' 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: M'(x,R) é incorreto}, então temos:

\forall x\,{\mbox{Prob}}_{R}[R\in {\mbox{Bad}}(x)]\leq {\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 é:

{\mbox{Prob}}_{R}[\exists x\,R\in {\mbox{Bad}}(x)]\leq {\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

Referências

↑ Lutz, Jack H.; Schmidt, William J. (1993), «Circuit size relative to pseudorandom oracles», Essex, UK: Elsevier Science Publishers Ltd., Theor. Comput. Sci., ISSN 0304-3975, 107 (1): 95–120
↑ Miltersen, Peter Bro. «Lecture notes on computational complexity» (PDF). Aarhus Universitet. Consultado em 4 de julho de 2022 ^{[ligação inativa]}
↑ «2.3: Strong probable-primality and a practical test». primes.utm.edu. Consultado em 4 de julho de 2022
↑ tcs-maam.dvi. [S.l.: s.n.] 1996. 29 páginas
↑ «Non-deterministic Exponential Time has Two-Prover Interactive Protocols». Consultado em 27 de abril de 2013. Arquivado do original em 31 de março de 2012
↑ «Na procura de uma testemunah fácil: Tempo Exponencial vs. Tempo Probabilístico Polinomial». Consultado em 27 de abril de 2013. Arquivado do original em 24 de março de 2012
↑ Bourke, Chris (2007). A Note on the Karp-Lipton Collapse for the Exponential Hierarchy. Lincoln, NE, EUA: University of Nebraska. 6 páginas
↑ Cai, Jin-Yi; Heck, Rachel; Kaiserlian, Chris; Langton, Asher (25 de fevereiro de 2003). «Lecture 11: Mahaney's Theorem» (PDF). Universidade de Vinconsin. CS 810: Introduction to Complexity Theory (810). 2 páginas. Consultado em 4 de julho de 2022
↑ Adleman, L. M. (1978), «Two theorems on random polynomial time», Symposium on Foundations of Computer Science|Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pp. 75–83, doi:10.1109/SFCS.1978.37