PP (complexidade)

Em Complexidade computacional, PP é a classe de problemas de decisão decidíveis por uma Máquina de Turing probabilística em tempo polinomial, com uma probabilidade de erro de menos do que 1/2 para todas as instâncias. A abreviação PP se refere a tempo polinomial probabilístico. A classe de complexidade foi definida[1] por Gill em 1977.

Se um problema de decisão está em PP, então existe um algoritmo para ele que se permite "jogar moedas para cima" e tomar decisões aleatórias. É garantido que ele rode em tempo polinomial. Se a resposta é SIM, o algoritmo vai responder SIM com uma probabilidade maior do que 1/2. Se a resposta for NÃO, o algoritmo vai responder SIM com uma probabilidade menor ou igual a 1/2. Em termos mais práticos, ela é a classe dos problemas que podem ser decididos para qualquer grau de precisão fixo rodando um algoritmo de tempo polinomial aleatoriamente por um número de vezes suficientes (mas limitado).

Uma caracterização alternativa para PP é o conjunto de problemas que pode ser resolvido por uma Máquina de Turing não determinística em tempo polinomial onde a condição de aceitação é que a maioria (mais da metade) dos caminhos de computação são aceitos. Por causa disso, alguns autores sugerem o nome alternativo Majority-P[2]

Definição

Uma linguagem L está em PP se e somente se existe uma máquina de turing probabilística M, que:

• M roda em tempo polinomial em todas as entradas.
• Para todo x em L, M da como saída 1 com probabilidade estritamente maior do que 1/2.
• Para todo x não estando em L, M da como saída 1 com probabilidade menor ou igual do que 1/2.

Alternativamente, PP pode ser definida usando apenas máquinas de Turing determinísticas. Uma linguagem L está em PP se e somente se existe um polinômio p e uma máquina de Turing M, que:

• M roda em tempo polinomial para todas as entradas
• Para todo x em L, a fração de strings y de tamanho p(|x|) que satisfaz M(x,y) = 1 é estritamente maior do que 1/2.
• Para todo x não estando em L, a fração de strings y de tamanho p(|x|) que satisfaz M(x,y) = 1 é menor ou igual a 1/2.

Em ambas definições, "menor ou igual a" pode ser mudado para "menor que"(veja abaixo), e o limite de 1/2 pode ser trocado por qualquer numero racional fixado em (0,1), sem mudança de classe.

PP vs BPP

BPP é um subconjunto de PP, ele pode ser visto como o subconjunto que contem algoritmos probabilísticos eficientes. A distinção está no erro probabilístico que é permitido: Em BPP, um algoritmo deve dar a resposta correta (SIM ou NÃO) com probabilidade excedendo alguma constante c fixada maior do que 1/2, como 2/3 ou 501/1000. Se for este o caso, então podemos rodar o algoritmo um numero polinomial de vezes e tomar a maioria dos votos para conquistar qualquer probabilidade de acerto desejada que seja menor do que 1, usando o Chernoff bound (link). Este numero de repetições aumenta se c chega perto de 1/2, mas ele não depende do tamanho da entrada n.

O importante é que seja permitido que a constante c dependa da entrada. Por outro lado, um algoritmo PP é permitido fazer algo do tipo:

• Em uma instância Sim, de como resultado SIM com probabilidade 1/2 + 1/2^n, onde n é o tamanho da entrada.
• Em uma instância Não, dê como saída SIM com probabilidade 1/2-1/2^n.

Pelo fato de estas duas probabilidades estarem tão próximas, especialmente no tamanho de n, então se rodarmos um número grande de vezes é muito difícil de dizer se estamos operando em uma instancia de SIM ou de NÃO. Tentar atingir um nível de probabilidade desejada fixo usando o voto da maioria e o Chernoff bound requer um número de repetições que é exponencial em n.

PP comparado a outras classes de complexidade

PP contém BPP, pois os algoritmos probabilísticos descritos na definição de BPP formam um subconjunto dos definidos em PP.

PP também contem NP (link). Para provar isto, nós mostramos que os problemas NP-completo pertencem a PP. Considere um algoritmo probabilístico que, dada uma fórmula F(x1, x2, ..., xn) escolhe uma atribuição x1,x2,...,xn uniforme e aleatoriamente. Então, o algoritmo checa se as atribuições fazem com que a fórmula F seja verdadeira. Se sim, ele dá como resposta SIM. Caso contrário, ele dá como saída SIM com probabilidade 1/2 e NÃO com probabilidade 1/2.

Se a fórmula é insatisfatível, o algoritmo sempre retornará SIM com probabilidade 1/2. Se existe uma atribuição que satisfaz, terá como saída SIM com probabilidade maior do que 1/2 (exatamente 1/2 se for escolhida uma atribuição que não satisfaz e 1 se for escolhida uma atribuição que satisfaz, com média próxima a algum número maior do que 1/2). Assim, este algoritmo coloca satisfabilidade em PP. Como SAT é NP-completa, e podemos prefixar qualquer redução por mapeamento de tempo polinomial determinístico no algoritmo PP, NP está contida em PP. Em razão do fato de que PP é fechada sob complemento, ela também contém co-NP.

Além disso, PP contém MA,[3] que agrupa as duas inclusões anteriores.

PP também contem BQP, a classe de problemas de decisão decidíveis por polinômios de tempo eficientes de computadores quânticos. De fato, BQP é Low para PP,significando que uma máquina PP não tem benefício algum por resolver problemas BQP instantaneamente. A classe de tempo polinomial em computadores quânticos com Postselection, PostBQP, é igual a PP[ref4].

Além disso, PP contém QMA, que abarca as inclusões de MA e BQP.

Uma máquina de Turing de tempo polinomial com um PP de Máquina oráculo (P^PP) pode resolver todos os problemas em en:PH (complexity), toda a Hierarquia polinomial. Este resultado foi mostrado por Seinosuke Toda em 1989 e é conhecido como Toda's theorem. Isto é evidencia do quanto é difícil resolver problemas em PP. A classe #PP é em algum sentido tão difícil quanto, por que P^#P = P^PP e portanto P^#P contém PH também.

PP estritamente contém TC^0, a classe de profundidade constante, uniformemente ilimitadada de circuitos boleanos com Função majoridade.(Allender 1996, como citado em Burtschick 1999).

PP está contido em PSPACE. Isto pode ser facilmente mostrado exibindo um algoritmo de espaço polinomial para MAJSAT, definida abaixo; simplesmente tente todas as atribuições e conte o numero de atribuições satisfatíveis.

PP não está contido em SIZE(n^k) para qualquer k (prova).

Problemas completos e outras propriedades

Diferentemente de BPP, PP é uma classe sintática, em vez de semântica. Qualquer máquina probabilística de tempo polinomial reconhece alguma linguagem em PP. Em contraste, dada uma descrição de uma máquina probabilística de tempo polinomial, no geral é indecidível determinar se ela reconhece uma linguagem em BPP.

PP tem problemas completos naturais, por exemplo, MAJSAT. MAJSAT é um problema de decisão em que é dada uma fórmula booleana F. A resposta deve ser SIM se mais da metade das atribuições de x₁, x₂, ..., x_n fazem com que F seja verdade, e NÃO caso contrário.

Prova de que PP é fechada sob complemento

Seja L uma linguagem em PP. Suponha que ${\displaystyle L^{c}}$ denote o complemento de L. Pela definição de PP existe um algoritmo probabilístico de tempo polinomial com a propriedade de que ${\displaystyle x\in L\Rightarrow \mathrm {Pr} [A\,\mathrm {aceita} \,x]>1/2}$ and ${\displaystyle x\not \in L\Rightarrow \mathrm {Pr} [A\,\mathrm {aceita} \,x]\leq 1/2}$. Alegamos que sem perda de generalidade, a última inequação é sempre estrita; uma vez que nós fazemos isto o teorema pode ser provado da seguinte forma. Seja ${\displaystyle A^{c}}$ a denotação da máquina que é igual a A exceto que ${\displaystyle A^{c}}$ aceita quando A rejeitaria, e vici-versa. Então ${\displaystyle x\in L^{c}\Rightarrow \mathrm {Pr} [A^{c}\,\mathrm {aceita} \,x]>1/2}$ and ${\displaystyle x\not \in L^{c}\Rightarrow \mathrm {Pr} [A^{c}\,\mathrm {aceita} \,x]<1/2}$, o que implica que ${\displaystyle L^{c}}$ está em PP.

Agora nós justificamos nossa suposição sem perda de generalidade. Seja ${\displaystyle f(|x|)}$ o limite superior polinomial no tempo de execução de A com uma entrada x. Assim A faz no máximo ${\displaystyle f(|x|)}$ escolhas aleatórias(jogar a moeda) durante suas execução. Em particular, ${\displaystyle x\in L\Rightarrow \mathrm {Pr} [A\,\mathrm {aceita} \,x]\geq 1/2+1/2^{f(|x|)}}$ desde que a probabilidade de aceitação seja um inteiro múltiplo de ${\displaystyle 1/2^{f(|x|)}}$. Defina uma máquina A' da seguinte forma: na entrada x, A' roda A como subrotina, e rejeita se A rejeitar; caso contrário, se A aceitaria, A' faria ${\displaystyle f(|x|)+1}$ escolhas aleatórias(jogar a moeda) e rejeitaria se todas fossem cara, e aceitaria caso contrário. Então ${\displaystyle x\not \in L\Rightarrow \mathrm {Pr} [A'\,\mathrm {aceita} \,x]\leq 1/2\cdot (1-1/2^{f(|x|)+1})<1/2}$ e ${\displaystyle x\in L\Rightarrow \mathrm {Pr} [A'\,\mathrm {aceita} \,x]\geq (1/2+1/2^{f(|x|)})\cdot (1-1/2^{f(|x|)+1})>1/2}$. Isto justifica a suposição(pois A' ainda é um algoritmo probabilístico de tempo polinomial) e completa a prova.

David Russo provou em sua tese de Ph.D em 1985[4] que PP é fechado sob Diferença simétrica. Era um problema em aberto por 14 anos se PP seria fechado sob união e Interceção; isto foi resolvido na afirmativa de Beigel, Reingold, e Spielman.[5] Provas alternativas foram dadas por Li[6] e Aaronson.

Outras classes de complexidade equivalentes

PostBQP

A classes de complexidade quântica BQP é a classes de problemas decidíveis em tempo polinomial em uma máquina de Turing quântica. Ao adicionar pós seleção, uma classe mais ampla chamada PostBQP é obtida. Informalmente, pós seleção da ao computador o seguinte poder computacional: a qualquer momento que algum evento (como medir um bit quântico em um certo estado) tem uma probabilidade diferente de zero, você pode assumir que ele está lá. [7] Scott Aaronson mostrou em 2004 que PostBQP é igual a PP.[8] Esta reformulação de PP torna mais fácil mostrar certos resultados, como os de que PP é fechada sob interseção (e consequentemente, sob união) que BQP é low para PP, e que QMA está contida em PP.

PQP

PP é também igual a outra classe de complexidade quântica conhecida como PQP, que é a analoga de erro ilimitada de BQP. Ela denota a classe dos problemas de decisão decidíveis por um computador quântico em tempo polinomial, com uma probabilidade de erro menor do que ½ para todas as entradas.

Referências

1. J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977.
2. Lance Fortnow. Computational Complexity: Wednesday, September 4, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html
3. N.K. Vereshchagin, "On the Power of PP"
4. David Russo (1985). «Structural Properties Of Complexity Classes». University of California, Santa Barbara. Ph.D Thesis 
5. R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991, pp. 1–9, 1991.
6. Lide Li (1993). «On the Counting Functions». University of Chicago. Ph.D Thesis 
7. Aaronson, Scott. «The Amazing Power of Postselection». Consultado em 27 de julho de 2009 
8. Aaronson, Scott (11 de janeiro de 2004). «Complexity Class of the Week: PP». Computational Complexity Weblog. Consultado em 2 de maio de 2008 

Bibliografia

• Papadimitriou, C. (1994). «chapter 11». Computational Complexity. [S.l.]: Addison-Wesley .
• Allender, E. (1996). «A note on uniform circuit lower bounds for the counting hierarchy». Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Col: Lecture Notes in Computer Science. 1090. [S.l.]: Springer-Verlag. pp. 127–135 .
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999). «Lindström Quantifiers and Leaf Language Definability» .