交互式证明系统

计算机学术语

在计算复杂性理论中，交互式证明体系（下简称交互证明）是一类计算模型。

简介

在计算复杂性理论中，像其它计算模型一样，我们的目标是对一个语言L，和一个给定的输入x，判断x是否在L中。交互式证明体系由两个实体：验证者（verifier）和证明者（prover）组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。

交互证明的基本假设是：证明者在计算能力上是无限的，而验证者一般设为多项式时间的、可使用随机源的图灵机。一般来说，对给定的L，我们关注的是交互证明中验证者V这一角色，并对它加以如下的要求：

完备性（completeness）：如果x∈L，那么存在诚实的证明者P，使得V与P的交互之后，输出“x∈L”；

可靠性（soundness）：如果x∉L，那么对任意的证明者P，V与P交互之后，输出“x∈L”的概率很小（可以认为小于某一常数）。

如果对L，这样的验证者存在，那么我们说L有这样的一个交互体系。

类似对图灵机所需的运行时间和空间等加以限制来得到语言的集合——复杂性类一样，通过改变交互证明中，交互过程的轮数、随机源是公开的还是验证者所私有的，以及证明者的数目等等参数，我们可以得到不同能力的证明体系，并依据一个语言是不是有这样参数的交互证明，来定义相应的语言的集合——复杂性类。依据交互证明定义的主要复杂性类有NP和AM，它们与依据图灵机定义的经典复杂性类的关系是重要的研究课题。

导致交互证明的发现的第一个观察是对NP的如下的理解：我们知道NP可以理解为解可以在多项式时间进行验证的问题的集合，而求这个解的过程可能是较为困难的，如对NP完备问题，现今仍未有多项式时间的算法。这样，“验证解”和“求解”这两项计算任务就有了计算能力上的差异。所以我们可以假设“验证解”是由验证者完成（在NP的情况下，是确定性多项式时间图灵机），而“求解”是由一个能力更强的图灵机完成的（在NP的情况下，可以假设是确定性指数时间图灵机）。下面我们用PTM代表确定性多项式时间图灵机。

于是从NP我们可以设计如下的交互证明：给定L∈NP，和x∈L，我们知道对x的一个解w，有一PTM，对输入(x, w)，输出“接受”当且仅当w是x的一个解。我们考虑一轮的，由证明者P发起的交互证明：

于是我们知道，NP是包含在轮数为1，交换信息长度为多项式的，验证者是确定性图灵机的证明体系中的。反过来，这样的证明体系定义的语言容易看出也是在NP中的。这样NP就与这样的证明体系等价。可以证明，当验证者是确定性图灵机，每轮交换信息长度为多项式的，即便将轮数扩展成多项式轮，所得到的交互证明仍然与NP是等价的。这样就需要将验证者扩展成随机性图灵机，此时我们就有了下面的有趣的复杂性类。

MIP

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

IPP

IPP（unbounded IP）是IP的一种变体，将原来的BPP检验者换成PP检验者。更精确的说，我们将完备性跟可靠性的条件修改如下：

虽然IPP仍旧与PSPACE相等，但是IPP协议系统在涉及启示图灵机的情况下与IP的状况差异颇大：对所有的启示图灵机IPP=PSPACE，但是几乎对所有的启示图灵机，IP≠PSPACE。

QIP

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

compIP

IPP跟QIP都是给予检验者更多的能力，但是一个compIP系统（competitive IP proof system）则是将证明者减弱如下：

零知识证明

零知识证明是一种特殊的交互式证明，其中证明者知道问题的答案，他需要向验证者证明“他知道答案”这一事实，但是要求验证者不能获得答案的任何信息。

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省