PCP (計算複雑性理論)

計算複雑性理論における PCP とは、確率的検査可能証明（probabilistically checkable proof）系を持つ決定問題の複雑性クラスである。

概要と定義

計算複雑性理論において、PCP 系は対話型証明系の一種と見ることができ、証明者がメモリを持たない神託機械であり、検証者が多項式時間の乱択アルゴリズムである。ある言語に属する入力（すなわち答えがYES）の場合、検証者が確実に受理する神託（証明）が存在する。答えがNOの入力の場合、神託がどうであれ、検証者はそれを少なくとも1/2の確率で拒絶する（co-RP参照）。

PCP の別の見方として、NP の強力版と見ることもできる。NPに属する言語について、証明の検証にかかる時間は少なくとも証明にかかる時間程度であるが、PCPに属する言語ではその限りではない。従って、PCPについての証明はNPよりも長くなる可能性がある。

上記の解説では、検証者が神託機械に問い合わせできる回数の上限を特に設定していない。PCP系の能力に影響するもう1つの要因として、検証者が実施できるコイントス回数がある。また、コイントス回数が増えれば、検証者はより厳密に証明を検証できる。従って PCP は実際には、2つの引数を持つ関数でパラメータ化された複雑性クラスのメタクラスと言うことができる。

PCP(r(·), q(·)) は、確率的検査可能証明のある言語のクラスであり、検証者は r(n) 回のコイントスと q(n) 回の神託機械への問い合わせが可能である（n は入力長）。

例

PCP アルゴリズムの多くは明確に説明するのが困難だが、3CNFSAT のための単純なアルゴリズムの考え方をここで解説する。3CNFSAT とは、各節に必ず3つのリテラルがある連言標準形（CNF）で構成される論理式についての充足可能性問題である。これはNP完全問題である。

m 個の変数と n 個の節からなる論理式 F があるとする。問題は、この論理式を真とするような m 個の変数の値の組合せがあるかどうかである。ただし、ここでは m 個の変数全部を調べるのではなく、O(log n) のランダムビット列で無作為に節を選択する。そして、その節内の変数について、3回の神託機械呼び出しを行って値を得る。それによってその節が真になるなら、検証者がその節を選んだのだから、1/n の確率でそれが真になることを確信できる。このアルゴリズムを n 回繰り返すと、O(nlog n) のランダムビット列と 3n 回の神託機械呼び出しで、ある誤り率を伴いつつ、NP完全問題（さらに全てのNP問題）を PCP(nlog n, n) に置くことができる。

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

単純な特殊ケース（poly は多項式的な量であることを意味し、log は対数的な量であることを意味する）:

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

その他の特筆すべき例:

PCP (poly, poly) = NEXP
もし NP = PCP (o(log), o(log)) なら NP = P となる。
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（PS）
A simplified proof of PCP (PDF, ？ KiB) - by Irit Dinur^{[リンク切れ]}