PP este un obiect al teoriei complexității , un domeniu al informaticii teoretice . Este o clasă de complexitate probabilistică. Mai precis, este setul de probleme de decizie decise de o mașină probabilistică de Turing în timp polinomial cu o probabilitate de eroare mai mică de jumătate.
Un limbaj L este în PP dacă există o mașină probabilistică Turing M, astfel încât:
Clasele BPP și PP sunt foarte asemănătoare din punct de vedere al definiției, dar a priori nu sunt egale. Într-adevăr, BPP este clasa de probleme care pot fi decise de o mașină în timp polinomial cu o probabilitate de răspuns corect mai mare decât o constantă în sine strict mai mare de 1/2. Prin urmare, BPP este inclus în PP .
Avem următoarele două incluziuni: NP este inclus în PP, care este inclus în PSPACE .
Teorema lui Toda afirmă că P Oracle PP conține PH , ierarhia polinomul ( Toda 1991 ).
PP este închis prin uniune și intersecție ( Beigel, Reingold și Spielman 1991 ).
PP are probleme complete, de exemplu MAJSAT: pentru o formulă F, mașina trebuie să accepte dacă și numai dacă F este adevărat pentru mai mult de jumătate din atribuțiile posibile pentru variabile.
Această clasă a fost introdusă de J. Gill în 1977 în articolul Complexitatea calculațională a mașinilor probabilistice Turing , în același timp cu clasele BPP , RP și ZPP ( Gill 1977 ).
Închiderea diferenței simetrice a clasei a fost demonstrată de David Russo în teza sa, iar închiderea uniunii și a intersecției a fost demonstrată în 1991, după ce a fost o problemă deschisă timp de 14 ani.
Relația dintre PP și ierarhia polinomială a câștigat Premiul Gödel din 1998 pentru Seinosuke Toda .