PP (計算複雑性理論)
BPPとは異なり、PP は意味論的ではなく文法的なクラスである。任意の確率的機械は、何らかの PP に属する言語を認識する。一方、ある確率的機械の説明を与えられても、それが BPP に属する言語を認識できるかどうかは判定できない。
MAJSAT問題は、PP完全問題である。
PP は補集合と対称差について閉じており、和集合と共通部分についても閉じている。後者2つの証明は前者2つよりずっと難しく、約14年間未解決の問題となっていた。
計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した。