交互式证明系统

维基百科,自由的百科全书
跳转至: 导航搜索

计算复杂性理论中,交互式证明体系(下简称交互证明)是一类计算模型。像其它计算模型一样,我们的目标是对一个语言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有这样的一个交互体系。

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

NP[编辑]

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

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

  • 证明过程:
    1. V和P商量好解的长度l,且l是输入的多项式;
    2. V和P接到输入x;
    3. P将解w送给V。不论P送多少字符,V只截取前l个;
    4. V运行M(x,w),输出“接受”当且仅当M输出“接受”。
  • 完备性:由L的性质,我们知道对x∈L,当且仅当有解w,使得M(x,w)接受。所以一个好的证明者将利用它无限的计算能力得到w,故V会接受;
  • 可靠性:同样由L的性质,当x∉L,不可能有解w,使得M(x,w)接受。所以一个坏的证明者将无法使V接受不在L中的x。

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


亚瑟-梅林协议(AM)和梅林-亚瑟协议(MA)[编辑]

我们保持轮数为1轮,由证明者发起,而将上面的PTM换作多项式时间随机性图灵机,那么我们得到了复杂性类MA。更一般的,我们将轮数扩展成不限1轮,而是常数轮时,我们得到的是叫AM的复杂性类。

IP[编辑]

MIP[编辑]

PCP[编辑]

零知识证明(Zero-knowledge proofs)[编辑]

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

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