PCP (計算複雑性理論)
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) に置くことができる。