交互式证明

事实上，这一类别很快就把复杂性理论家们迷住了，原因如下：GMR的交互式证明是针对已经在NP内的问题的。

我们用IP表示这类交互式证明语言。

在该文中她证明NP正好是验证者只有对数空间和对证明的单向阅读权时的交互式证明语言类。

Babai想要得到一个无条件结果，于是他独立地引入了交互式证明的概念，尽管用的是公开硬币抛掷，并且证实他的问题具有常数轮次的交互式证明。

特别地，在STOC'88上，为了从关于零知识证明的一些结果中去除加密的假定，Michaelben-Or，Goldwasser,JoeKilian与Wigderson引入了多方交互式证明的概念：

又过了稍长的一段时间，交互式证明的复杂性依然风平浪静。

PCP定理的故事是1980年代从麻省理工学院开始的，起源于获得史上首届Gödel奖的一篇论文：《交互式证明体系的知识复杂性》，作者是Goldwasser,Micali与Rackoff。