PP je předmětem teorie složitosti , oblasti teoretické informatiky . Je to třída pravděpodobnostní složitosti. Přesněji řečeno, jedná se o soubor rozhodovacích problémů, o nichž rozhoduje pravděpodobnostní Turingův stroj v polynomiálním čase s pravděpodobností chyby menší než polovina.
Jazyk L je v PP, pokud existuje pravděpodobnostní Turingův stroj M, takový, že:
Třídy BPP a PP jsou si velmi podobné z hlediska definice, ale a priori nejsou stejné. Ve skutečnosti je BPP třídou problémů, o kterých může rozhodovat stroj v polynomiálním čase s pravděpodobností správné odezvy větší než konstanta přísně větší než 1/2. BPP je proto součástí PP .
Máme následující dvě inkluze: NP je zahrnuto v PP, které je zahrnuto v PSPACE .
Na Toda teorém říká, že P oracle PP obsahuje PH , je polynom hierarchii ( Toda 1991 ).
PP je uzavřen spojením a křižovatkou ( Beigel, Reingold a Spielman 1991 ).
PP má úplné problémy, například MAJSAT: pro vzorec F musí stroj přijmout právě tehdy, když F je pravdivé pro více než polovinu možných přiřazení proměnných.
Tuto třídu představil J. Gill v roce 1977 v článku Výpočetní složitost pravděpodobnostních Turingových strojů , současně s třídami BPP , RP a ZPP ( Gill 1977 ).
Symetrický rozdíl uzavření třídy prokázal David Russo ve své práci a uzavření unie a křižovatky bylo prokázáno v roce 1991 poté, co byl otevřeným problémem po dobu 14 let.
Vztah mezi PP a polynomiální hierarchií získal v roce 1998 Gödelovu cenu pro Seinosuke Toda .