PCP (計算複雑性理論)
計算複雑性理論において、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 は入力長)。
単純な特殊ケース(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)) である。これは、近似アルゴリズムのために計算困難性を証明するのに役立つ。