PCP (計算複雑性理論)

PCP（確率的検査可能証明）についての解説

計算複雑性理論において、PCP（Probabilistically Checkable Proof）とは、確率的に検査可能な証明を持つ決定問題の複雑性クラスを指します。この理論は、対話型証明系の一形態として理解され、証明者がメモリを持たない設定で証明を行い、検証者は多項式時間のランダム化アルゴリズムを使用して結果を評価します。具体的には、入力がある言語に属する場合、検証者は必ずその証明を受理しますが、逆に、入力がその言語に属さないものの場合、どんな証明であっても、少なくとも1/2の確率で拒否されるという性質を持っています。

PCPは、従来のNP（非決定性多項式時間）クラスの強化版とも考えられます。NPクラスに属する問題では証明の検証にかかる時間が証明そのものの大きさに比例していますが、PCPクラスでは必ずしもその制限を受けないため、証明がより長くなる可能性があります。

PCPの定義には、検証者が神託機械に問い合わせできる回数の制限が設けられない点が特徴的です。また、検証者が実施できるコイントスの回数もPCPの特性に影響を与えます。このコイントス数が増加するほど、検証者は証明をより厳密に確認できるため、PCPは、引数に応じた関数で定義される複雑性のメタクラスと位置づけることができます。

この理論の具体例として、PCP(r(·), q(·))という表現があり、この場合、r(n)回のコイントスとq(n)回の神託機械への問い合わせを通じて、言語のクラスが確率的に検査可能であることを示します（ここでnは入力の長さを示します）。

例：3CNFSAT問題

PCPアルゴリズムを理解する際、3CNFSAT（3つのリテラルを持つ各節からなる論理式の充足可能性問題）は良い例です。これはNP完全問題とされ、m個の変数とn個の節からなる論理式Fを考えます。この場合、求めるのは、与えられた論理式が真になるような変数の組合せです。

しかし、全ての変数を調べるのではなく、O(log n)のランダムビット列を用いて無作為に節を選び出し、それに対して3回の神託機械による問い合わせを行ってその値を得るアプローチが取られます。選ばれた節が真となる確率は、1/nとなるため、triestsを実施することで、結果としてPCP(n log n, n)に全NP問題を埋め込むことが可能になります。

他の複雑性クラスとの関連性

複雑性クラスとしてのPCPは、他のクラスとの関係性が興味深く、以下のような特性があります。

• - PCP (0, 0) = P
• - PCP (poly, 0) = Co-RP
• - PCP (0, poly) = NP

より複雑ですが重要な関係もあり、例えば、PCP (poly, poly) = NEXPと示され、場合によってはNP = PCP (o(log), o(log))、NP = PCP (log, poly)といった論理的つながりもあります。特に、PCP定理はNPがPCP (O(log n), O(1))に等しいとし、このことが近似アルゴリズムの計算困難性の証明に寄与しています。

参考文献

• - PCP notes and slides - by Madhu Sudan
• - PCP course notes - by Subhash Khot
• - Survey, a good starter - by Luca Trevisan
• - A simplified proof of PCP (PDF) - by Irit Dinur

もう一度検索