対話型証明系
なぜなら証明者の計算能力は無限なので、ランダムビット列さえ分かれば、検証者の計算を全てシミュレート可能だからである。ランダムビット列(硬貨投げ)が両方のマシンから見えるため、これを「公開硬貨」プロトコルと呼ぶ。一方 IP の手法を対照的に「秘密硬貨」プロトコルと呼ぶ。
公開硬貨の基本的な問題は次のようなものである。証明者が言語に属さない文字列を検証者に悪意を持って受理させようとした場合、検証者が内部状態を見せないようにするためにして証明者の計画を妨害する可能性がある。この問題があるため、IP 証明系が定義された。
1986年、ゴールドワッサーとシプサーは驚くべき結果を示した。すなわち、IP で認識できる言語は、Arthur-Merlin 公開硬貨プロトコルでも2ラウンド追加するだけで認識可能であり、結果としてほとんど差がないことがわかったのである。つまり、公開硬貨プロトコルも秘密硬貨プロトコルもほぼ同じであることが示された。実際、Babai は 1988年、任意の定数 k について AM[k] が IP[k] と比較して劣らないことを示した。
よく知られている複雑性クラス NP は非常に単純な対話型証明系で定式化できる。この場合、検証者は決定的な多項式時間の機械である(つまり、Pマシン)。プロトコルは次の通り。
証明者は入力を見て、その無限の計算能力を使って解を計算し、証明の証拠となる多項式長のメッセージを返す。
検証者はその証拠を決定的な多項式時間で検証する。妥当であれば、それを受理し、そうでなければ拒絶する。
妥当な証明の証拠がある場合、証明者は常に検証者が受理するような証拠を与えることができる。妥当な証明の証拠がない場合、入力が言語に属していないということであり、いかなる証拠も受理されないので、悪意のある証明者であったとしても検証者を納得させられない。
これらは、検証者に完全な解法が任せられない場合に重要となる。一見して、検証者が解法を知らないのに解法があるかどうかを判断するのは不可能に思われるが、NP に属するあらゆる問題にはいわゆるゼロ知識証明があると信じられており、暗号理論にとって重要である。ゼロ知識証明はゴールドワッサーらの IP に関する論文で提唱された概念だが、その能力の範囲を明らかにしたのは Oded Goldreich であった。
この強力なマシンの前では、多くの問題が簡単に解かれるようであった。1992年、アディ・シャミアは計算複雑性理論の重要な成果となる事実、IP = PSPACE を証明した。PSPACE は決定性チューリング機械で多項式領域を使って解ける問題のクラスである。確率的対話プロトコルと古典的な決定性機械の間のこの強い関係は、対話型証明系の能力と限界の概念を与え、2つの分野の重要な繋がりを確立した。