交互式证明系统

MIP

在1988年，Goldwasser et al.基于IP创造了另一个更强的交互式证明系统MIP，它包含两个独立的证明者。一旦检验者开始跟证明者沟通的时候，这两位证明者就不能互相沟通。多了一个证明者让检验者可以检查第一个证明者的证明，会让避免检验者被证明者欺骗的工作变得更简单，就像犯人自白时让他与他的同伙分开在两个无法互相沟通的地方自白时会比较容易找出他们是否说谎一样。事实上，这一件事的差异大到Babai, Fortnow，和Lund证明了MIP = NEXPTIME，这类问题是在指数时间之内以非决定性解的出来的问题，这是一个非常大的类别。此外，在MIP系统内，即使不做任何多余的假设，所有的NP语言均有零知识证明；在IP里面唯有假设存在单向函式才可能成立。

QIP

QIP是将IP的BPP检验者换成一个BQP检验者所产生的变体，说更明白些，BQP是可以用量子计算机在多项式时间内解决的问题类别。并且，这一些讯息是用量子位所表示的。在2009年, Jain, Ji, Upadhyay，和Watrous证明了QIP也与PSPACE相等，总结起以上Kitaev和Watrous的理论，我们得到QIP包含在EXPTIME内的结论，因为QIP = QIP[3]，so that more than three rounds are never necessary.

零知识证明（Zero-knowledge proofs）

零知识证明是一种特殊的交互式证明，其中证明者知道问题的答案，他需要向验证者证明“他知道答案”这一事实，但是要求验证者不能获得答案的任何信息。
可以参考这样一个简单的例子。证明者和验证者都拿到了一个数独的题目，证明者知道一个解法，他可以采取如下这种零知识证明方法：他找出81张纸片，每一张纸片上写上1到9的一个数字，使得正好有9份写有从1到9的纸片。然后因为他知道答案，他可以把所有的纸片按照解法放在一个9乘9的方格内，使得满足数独的题目要求（每列、每行、每个九宫格都正好有1到9）。放好之后他把所有的纸片翻转，让没有字的一面朝上。这样验证者没办法看到纸片上的数字。接下来，验证者就验证数独的条件是否满足。比如他选一列，这时证明者就把这一列的纸片收集起来，把顺序任意打乱，然后把纸片翻过来，让验证者看到1到9的纸片都出现了。整个过程中验证者都无法得知每张纸片的位置，但是却能验证确实是1到9都出现了。