PP (complexidade): diferenças entre revisões

Conteúdo apagado Conteúdo adicionado
Etiquetas: Edição via dispositivo móvel Edição feita através do sítio móvel
Etiquetas: Edição via dispositivo móvel Edição feita através do sítio móvel
Linha 33:
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 algorítimoalgoritmo 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 algorítimoalgoritmo sempre retornará SIM com probabilidade 1/2. Se existe
uma atribuição que satisfaz, terá como saidasaí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 algorítimoalgoritmo coloca satisfabilidade em PP. Como SAT é NP-completa, e podemos prefixar qualquer redução por mapeamento de tempo polinomial determinístico no algorítimoalgoritmo 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,<ref>[http://lpcs.math.msu.su/~ver/papers/am-pp.ps N.K. Vereshchagin, "On the Power of PP"]</ref> que agrupa as duas inclusões anteriores.
Linha 48:
PP estritamente contém '''[[TC0|TC<sup>0</sup>]]''', 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 algorítimoalgoritmo de espaço polinomial para MAJSAT, definida abaixo; simplesmente tente todas as atribuições e conte o numero de atribuições satisfativeissatisfatíveis.
 
PP não está contido em '''SIZE'''(n<sup>k</sup>) para qualquer k ([[:en:Karp-Lipton theorem#Application to circuit lower bounds – Kannan's theorem|prova]]).