PP er et objekt av kompleksitetsteori , et felt med teoretisk informatikk . Det er en klasse med sannsynlig kompleksitet. Mer presist er det settet med avgjørelsesproblemer avgjort av en sannsynlig Turing-maskin i polynomisk tid med en feilsannsynlighet mindre enn halvparten.
Et språk L er i PP hvis det finnes en sannsynlig Turing-maskin M, slik at:
BPP- og PP- klassene er veldig like når det gjelder definisjon, men a priori er ikke like. Faktisk er BPP klassen av problemer som kan avgjøres av en maskin i polynomisk tid med en sannsynlighet for riktig svar større enn en konstant i seg selv strengt større enn 1/2. BPP er derfor inkludert i PP .
Vi har følgende to inkluderinger: NP er inkludert i PP som er inkludert i PSPACE .
Den Toda teorem angir at P kor PP inneholder PH , den polynomiske hierarki ( Toda 1991 ).
PP er stengt av fagforening og kryss ( Beigel, Reingold og Spielman 1991 ).
PP har fullstendige problemer, for eksempel MAJSAT: for en formel F, må maskinen godta hvis og bare hvis F er sann i mer enn halvparten av de mulige oppdragene for variablene.
Denne klassen ble introdusert av J. Gill i 1977 i artikkelen beregningskompleksitet av sannsynlighets Turing maskiner , samtidig som den BPP , RP og ZPP klasser ( Gill 1977 ).
Den symmetriske forskjellslukkingen av klassen hadde blitt demonstrert av David Russo i sin avhandling, og stengningen av fagforeningen og krysset ble demonstrert i 1991 etter å ha vært et åpent problem i 14 år.
Forholdet mellom PP og polynomet hierarkiet vant 1998 Gödel Prisen til Seinosuke Toda .