PP (計算複雑性理論)
PP に属する決定問題には、コインを投げて無作為に決定を行うアルゴリズムが存在する。その時間計算量は多項式時間以内であることが保証される。解が YES なら、そのアルゴリズムは 1/2 より高い確率で YES を返す。解が NO なら、そのアルゴリズムは最大でも 1/2 の確率で YES を返す。より実用的な観点では、このクラスに属する問題は、無作為ながらも多項式時間である一定の確率で正しい答えを返すので、それを適当な回数繰り返すことで十分な精度で解を得ることができる。
PP は、非決定性チューリング機械で多項式時間で解ける問題の集合と定義することもでき、その場合、計算経路の半数以上で受理されたとき、全体として受理されたと判断する。このため、PP のことを Majority-P と呼ぶことがある。