P/polinomial

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde abril de 2013).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.


Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.

Na Teoria da complexidade computacional, P/poly é a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma máquina de Turing with a 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 Miller-Rabin primality teste 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 encontrar-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 PSPACE' P/polinomial então PSPACE = \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 protocoloMA: Merlin envia o circuito como prova, e Arthur pode simular protocolo IP ele mesmo sem qualquer ajuda adicional.
  • Se P #PP/polinomial então P#P = MA.[5] A prova é semelhante a anterior, com base em um protocolo interativo para permanente e #P-completude de permanente.
  • Se EXPTIMEP/polinomial então EXPTIME = \Sigma_2^{\rm P} \cap \Pi_2^{\rm P} (Teorema de Meyer), inclusive EXPTIME = MA.
  • Se NEXPTIMEP/polinomial então NEXPTIME = EXPTIME, inclusive NEXPTIME = MA. Reciprovamente, NEXPTIME = MA implica NEXPTIMEP/polinomial[6]
  • If EXPNPP/polinomial then EXPNP = \Sigma_2^{\rm P} \cap \Pi_2^{\rm P} (Buhrman, Homer) [7]
  • É sabido que MAEXP, uma versão exponencia do MA, não está contido em P/polinomial.
Prova: Se MAEXPP/polinomial então PSPACE = MA (veja acima). By padding, EXPSPACE = MAEXP, portanto EXPSPACEP/polinomial mas isso pode ser provado como falso através da diagonalização.

Uma das razões mais interessantes que 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 serem linguagens esparsas, existe uma redução em tempo polinomial a uma máquian 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.

Prova[editar | editar código-fonte]

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 é o 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 (ver BPP). Se conseguirmos corrigir R,então, obtém-se um algoritmo que é deterministico.

Se Bad(x) é definido por {R: M'(x,R) é incorreto}, nós temos:

\forall x\, \mbox{Prob}_R[R \in \mbox{Bad}(x)] \leq \frac{1}{e^n}.

O tamanho da entrada é n, por isso existem duasn possíveis entradas. Assim, a probabilidade de que um R aleatório é bad 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 é bad para algun x é inferior a 1, por isso deve haver um R que é bom para todo x. Tome um R para ser a string de aconselhamento em nosso algoritmo P/polinomial.

Veja também[editar | editar código-fonte]

References[editar | editar código-fonte]

Predefinição:ComplexityClasses