PP (計算複雑性理論)

PP（確率的多項式時間）とは

PPは計算複雑性理論のクラスの一つであり、1977年にジョン・ギルによって提唱されました。このクラスは、確率的チューリング機械が多項式時間内に解ける決定問題の集まりであり、解を誤る確率は常に1/2未満であることが求められます。PPの名前は「確率的多項式時間」を意味しています。

PPに属する問題の特徴

PPには、コインを投げるなどの無作為な方法で決定を行うアルゴリズムが存在します。これらのアルゴリズムは、計算にかかる時間が多項式時間内であることが保証されています。もし解がYESであれば、そのアルゴリズムは1/2より高い確率でYESを返します。一方、解がNOであれば、最大でも1/2の確率でYESを返すことになります。このため、PPに属する問題は、無作為ながらも一定の確率で正しい答えを提供するため、繰り返し実行することで十分な精度で解を得ることが可能です。

PPクラスは、非決定性チューリング機械によって多項式時間で解決できる問題の集合とも関連しています。この場合、計算経路の過半数で受理されれば、全体として受理されたと見なされることから、PPは「Majority-P」とも称されます。

PPとBPPの違い

PPの部分集合として位置づけられるBPP（ボルツマン多項式時間）は、より効率的な乱択アルゴリズムに基づくものです。その最大の違いは、解を誤る確率の設定にあります。BPPの場合、解が正しく返される確率は1/2より高い任意の定数c（例えば2/3や501/1000）で示されます。BPPでは、確率が入力の長さに依存しないため、アルゴリズムを繰り返し実行することで、チェルノフ限界を用いて、高い確率で正しい結果を得ることができます。

PPのアルゴリズムでは、解がYESの場合に限り、YESを返す確率は1/2 + 1/2^nとなります。ここでnは入力の長さを指します。NOが正解であればYESを確率1/2で返すため、確率が非常に近似しているため、結果の精度を上げるためには何度も試行が必要となります。これを理解するためには、細工を施したコインを繰り返し投げて、そのどちらの面が出やすいかを確かめるイメージが分かりやすいでしょう。

PPと他の複雑性クラスの関係

PPはBPPを含むだけでなく、NPクラスも含んでいます。NP完全問題である充足可能性問題をPPに属することを示せば、これが成り立ちます。論理式F(x1, x2, ..., xn)に対してランダムに変数の値を決定し、その結果としてFが真になるかを計算するアルゴリズムにおいて、Fが真の場合にはYES、そうでない場合には確率1/2でYESまたはNOを返します。PPクラスは補問題にも閉じているため、co-NPもPPに含まれます。

さらに、PPはBQP（量子計算で効率的に解ける問題のクラス）も含むことが知られています。この関係は、BQPの解法がPPの効率に影響を与えないことを示唆しています。

PPの神託機械を備えた多項式時間のチューリングマシン（PPP）は、ポリノミアル階層（PH）全体の問題を解決可能です。この特徴は、PPに属する問題の解決が非常に難しいことを示すものとなっています。

最後に、PPはTC0を厳密に包含しており、PSPACEにも含まれることが示されています。いずれも、これらの問題がどのように結びついているかを理解することで、計算複雑性理論の詳細な構造を理解する手助けとなるでしょう。

結論

PPは計算の効率性と確率を組み合わせた強力なクラスであり、他の複雑性クラスとの関係を深く理解することで、計算理論の枠組みの中での位置づけをより明確にすることができます。

もう一度検索