対話型証明系
Babai がMAの証明系を定義した直後、シャフィ・ゴールドワッサーらは IP[f(n)] の対話型証明系を定義した論文のドラフト版を発表した。これは MA プロトコルと同様のマシン構成だが、入力長 n に対して f(n) 回のラウンドが許されていた。各ラウンドで、検証者は計算を行って証明者にメッセージを渡し、証明者も計算を行って検証者にメッセージを返す。そして全ラウンドの最後に検証者は決定しなければならない。例えば、IP[3] プロトコルなら、メッセージの並びは VPVPVPV となる。ここで、V は検証者のターン、P は証明者のターンである。
Arthur-Merlin プロトコルでは、Babai は同様のクラスを AM[f(n)] と定義した。これも f(n) 回のラウンドを許すものだが、彼はマシンに条件を1つ追加した。検証者は証明者に対して計算に使用したランダムビット列を全て提示しなければならないというものである。結果として検証者は証明者に対して何も隠せないことになる。
Arora と Safra の最初の重要な成果は PCP(log, log) = NP を示したことである。これを言い換えると、NP プロトコルの検証者が証拠のうちの log n ビットだけを調べ、log n 個のランダムビットを使うと、普通の NP プロトコルと差が生じないのである。
それだけではない。Arora と Safra はランダムビット数とアクセスビット数を同時に少なくしても意味がないことを知っていたが、彼らは一方だけを小さくできると信じていた。Arora らは最終的にこれをPCP定理としてまとめた。これは、証明結果へのアクセスを定数にまで低減させることができることを示したものである。すなわち、NP = PCP(log, O(1)) である。彼らはこの NP の性質を使って、P = NP でない限り、一部のNP完全問題の最適化版に近似アルゴリズムが存在しないことを証明した。