PP (計算複雑性理論)
BQP は量子コンピュータで効率的な多項式時間で解ける決定問題のクラスである。実際、BQP は PP に対して low である。すなわち、BQP を即座に解ける方法があったとしても PP を解く効率は変わらない。
PPの神託機械を持つ多項式時間のチューリングマシン(P)は、PH すなわち多項式階層全体に属する全問題を解くことができる。これは戸田誠之助が1989年に示したもので、「戸田の定理」と呼ばれている。これは PP に属する問題を解くのがいかに困難であるかの証拠である。クラス #P は、P = P であり、P も PH を包含するため、PP と同程度に困難と考えられる。
PP は TC を厳密に包含している。このクラスは回路計算量に関するもので、一定の深さと無制限の入力端子数の論理回路に多数決回路を持っている(Allender 1996, as cited in Burtschick 1999)。
PP は PSPACE に包含される。これは MAJSAT 問題を多項式領域で解くアルゴリズムを示せば、容易に証明できる。MAJSAT 問題とは、充足可能問題について、あらゆる組合せを試して、式が真となる組合せを数え上げ、過半数が真なら YES となる問題である。