PPと他の複雑性クラスの比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/27 03:33 UTC 版)
「PP (計算複雑性理論)」の記事における「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 も包含する。BQP は量子コンピュータで効率的な多項式時間で解ける決定問題のクラスである。実際、BQP は PP に対して low である。すなわち、BQP を即座に解ける方法があったとしても PP を解く効率は変わらない。 PPの神託機械を持つ多項式時間のチューリングマシン（PPP）は、PH すなわち多項式階層全体に属する全問題を解くことができる。これは戸田誠之助が1989年に示したもので、「戸田の定理」と呼ばれている。これは PP に属する問題を解くのがいかに困難であるかの証拠である。クラス #P は、P#P = PPP であり、P#P も PH を包含するため、PP と同程度に困難と考えられる。 PP は TC0 を厳密に包含している。このクラスは回路計算量に関するもので、一定の深さと無制限の入力端子数の論理回路に多数決回路を持っている(Allender 1996, as cited in Burtschick 1999)。 PP は PSPACE に包含される。これは MAJSAT 問題を多項式領域で解くアルゴリズムを示せば、容易に証明できる。MAJSAT 問題とは、充足可能問題について、あらゆる組合せを試して、式が真となる組合せを数え上げ、過半数が真なら YES となる問題である。
※この「PPと他の複雑性クラスの比較」の解説は、「PP (計算複雑性理論)」の解説の一部です。
「PPと他の複雑性クラスの比較」を含む「PP (計算複雑性理論)」の記事については、「PP (計算複雑性理論)」の概要を参照ください。
- PPと他の複雑性クラスの比較のページへのリンク
