PP (計算複雑性理論)
上述の通り、PP は BPP を包含する。
PP は NP も包含する。これを証明するには、NP完全問題である充足可能性問題が PP に属することを示せばよい。論理式 F(x1, x2, ..., xn) について無作為に x1, x2, ..., xn の値を決め、それを使って F が真となるか計算してみるアルゴリズムを考える。F が真となったら YES を返し、そうでなければ確率 1/2 で YES、確率 1/2 で NO を返す。
その論理式が充足不可能な場合、このアルゴリズムは YES を確率 1/2 で返す。充足可能な組合せがある場合、YES を返す確率は 1/2 以上である(正確には、充足可能な組合せが得られない場合には 1/2 で、充足可能な組合せが偶然得られた場合は 1 であり、平均すると 1/2 より大きい適当な値となる)。従って、このアルゴリズムは PP に属し、充足可能性問題を解くことができる。SAT(充足可能性問題)はNP完全問題であり、PPのアルゴリズムに決定的な多項式時間多対一還元を前置することができるので、NP は PP に含まれることになる。PP は補問題について閉じているため、co-NP も PP に含まれる。
PP は BQP も包含する。