Saltar para o conteúdo

P/polinomial

Origem: Wikipédia, a enciclopédia livre.

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

[editar | editar código-fonte]

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 NPP/polinomial então PH (a hierarquia polinomial) cai para . Este resultado é o teorema de Karp-Lipton. Além disso, NPP/polinomial implica em AM = MA[4]
  • Se PSPACE'⊆ P/polinomialentãoPSPACE = , 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 #PP/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 EXPTIMEP/polinomial então EXPTIME = (Teorema de Meyer), inclusive EXPTIME = MA.
  • Se NEXPTIMEP/polinomial então NEXPTIME = EXPTIME, inclusive NEXPTIME = MA. Reciprocamente, NEXPTIME = MA implica NEXPTIMEP/polinomial.[6]
  • Se EXPNPP/polinomial então EXPNP = (Buhrman, Homer).[7]
  • É sabido que MAEXP, uma versão exponencial do MA, não está contido em P/polinomial.
Prova: Se MAEXPP/polinomial então PSPACE = MA (veja acima). Por padding, EXPSPACE = MAEXP, portanto EXPSPACEP/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 PNP. Esta observação foi o centro de muitas tentativas de provar que PNP.

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

[editar | editar código-fonte]

O Teorema de Adleman, provado por Leonard Adleman, afirma que BPPP/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.

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 n 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:

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

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.

Referências

  1. 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 
  2. Miltersen, Peter Bro. «Lecture notes on computational complexity» (PDF). Aarhus Universitet. Consultado em 4 de julho de 2022 [ligação inativa] 
  3. «2.3: Strong probable-primality and a practical test». primes.utm.edu. Consultado em 4 de julho de 2022 
  4. tcs-maam.dvi. [S.l.: s.n.] 1996. 29 páginas 
  5. «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 
  6. «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 
  7. Bourke, Chris (2007). A Note on the Karp-Lipton Collapse for the Exponential Hierarchy. Lincoln, NE, EUA: University of Nebraska. 6 páginas 
  8. 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 
  9. 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