対話型証明系
IP 設計者の目標は最も強力な対話型証明系の構築であり、当初それ以上に強力にするには検証者をさらに強力にする必要があり、現実的でないと思われていた。ゴールドワッサーらは 1988年、"Multi prover interactive proofs[...]" という論文でこれを打ち破り、IP の新たなバージョン MIP を定義した。これは証明者が独立して2つ存在する証明系である。
2つの証明者は、検証者がそれらにメッセージを送り始めたら、相互の通信はできなくなる。証明者は別々の部屋に入れられているようなもので、共謀して検証者を騙すことはできない。従って、どちらかが悪意を持って検証者を騙そうとしてもその検出が容易となる。
実際、Babai、Fortnow、Lund の3人は IP = PSPACE であることから MIP = NEXPTIME を導出した。これは、非決定性チューリング機械で「指数関数時間」で解ける問題の集合であり、非常に大きなクラスである。証明者を2つより多くしても、さらに言語が認識できるようにはならない。この結果に触発されて後述する PCP が設計された。PCP はスケールダウンしたバージョンであり、NP に関する対話型証明系である。
NPに属する各言語がゼロ知識証明を持つことを説明するに際して、IP では一方向性関数の存在を仮定する必要があったが、MIP ではそれが不要となる。これは、解読不能な暗号アルゴリズムの設計と関係がある。さらに、MIP プロトコルは IP に属する全言語を定数回のラウンドだけで認識でき、3つめの証明者を追加すると NEXPTIME に属する全言語を定数回のラウンドで認識できる。