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
Se a fórmula é insatisfatível, o
uma atribuição que satisfaz, terá como
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
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]]).
|