交互式证明系统

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

交互证明的基本假设是：证明者在计算能力上是无限的，在概率多项式时间（BPP (複雜度)）的图灵机。一般来说，对给定的L，我们关注的是交互证明中验证者V这一角色，并对它加以如下的要求：

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

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

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

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

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

• 证明过程：

*# V和P商量好解的长度l，且l是输入的多项式；
*# V和P接到输入x；
*# P将解w送给V。不论P送多少字符，V只截取前l个；
*# 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是等价的。这样就需要将验证者扩展成随机性图灵机，此时就有了下面的有趣的复杂性类。

梅林-亚瑟协议（MA）
保持轮数为1轮，由证明者发起，而将上面的PTM换作概率多项式时间图灵机，可以得到复杂性类MA:验证者是一个在概率多项式时间中的图灵机（亚瑟），证明者（梅林）给出对于问题的解之后，验证者必须在1/3的错误率以内决定n是否在这个语言之内。
更正式地说：

对任何语言L, L \in MA若\exists P, Q是多项式| \forall M, M \in PTM| \forall x, n = |x|：

若x在L*中, 那么 \exists z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\ge2/3,
若x不在L*中, 那么 \forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=0)\ge2/3.

第二个条件也可以被写为：
若x不在L*中, 那么 \forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\le1/3.

亚瑟-梅林协议（AM）
IP
在计算复杂性理论内，IP是由以下特定交互式证明系统所能解决的一类问题：验证者是一个在概率多项式时间的图灵机，双方可以交换多项式p(n)次信息，最后验证者必须在1/3的错误率以内决定n是否在这个语言之内。（所以在BPP内的语言一定在IP之内，因为我们可以让验证者直接忽略证明者然后自己对这问题作决定。）
更正式的说：

对任何语言L, L \in IP若\exists V, P | \forall Q, w:

• w \in L \Rightarrow \Pr[V \leftrightarrow P\text{ accept }w] \ge \frac{2}{3}
• w \not \in L \Rightarrow \Pr[V \leftrightarrow Q\text{ accept }w] \le \frac{1}{3}。

和AM不同之处在于，它的交换信息次数是被常数次数而非被一个多项式次数所限定。

IP = PSPACE
要证明IP与PSPACE相等，我们先证明出IP是PSPACE的子集，然后证明PSPACE也是IP的子集，因此之故两个集合相等。要证明出\text{IP} \subseteq \text{PSPACE}，我们展现出一个用多项式空间的机器可以怎样模拟一个交互式证明系统。要证明\text{PSPACE} \subseteq \text{IP}这一件事，我们推导一个PSPACE-完全语言TQBF是在IP里面。这两个部份的证明均是由Sipser提出的。

• IP是PSPACE的子集

设A是IP里的一个语言。 对于一个长度为n的输入w，A'的检验者V 正好交换 p=p(n) 条信息.我们现在建立一个机器M来模拟V，并且M是PSPACE机器。 为了达到这个目的，我们定义M如下：

: \Pr[V\text{ accepts }w] = \max_P \Pr[V \leftrightarrow P\text{ accepts } w]

根据\text{IP}的定义, 我们有：如果 w \not \in A，\Pr[V\text{ accepts }w] \ge \frac{2}{3} ；如果 w \in A 且 \Pr[V\text{ accepts }w] \le \frac{1}{3} 。

现在，我们可以定义：

: \Pr[V\text{ accepts }w\text{ starting at }M_j] = \max_P \Pr[V \leftrightarrow P\text{ accepts }w\text{ starting at }M_j]

并且对任何0 \leq j \leq p和每一条历史信息 M_j，我们归纳定义这个函数N_{M_j}如下：

:
N_{M_j} =
\begin{cases}
0: j = p\text{ and }m_p = \text{reject}\\
1: j = p\text{ and }m_p = \text{accept}\\
\max_{m_{j+1}} N_{M_{j+1}}: j

其中， \text{wt-avg}_{m_{j+1}}N_{M_{j+1}}被定义为:

: \text{wt-avg}_{m_{j+1}}N_{M_{j+1}} = \sum_{m_{j+1}}(Pr_r[V(w,r,M_j)])

• PSPACE是IP的子集

为了展示我们证明PSPACE \subseteq IP的方法，我们先证明一个比较弱的理论：\#SAT \in IP（最早由Lund, et al.证明）。然后利用这个证明的概念去证明TQBF \in IP。既然TQBF \in PSPACE-完全，我们可以得知若TQBF \in IP则PSPACE \subseteq IP，因此证明PSPACE \subseteq IP.

• #SAT是IP的其中一个语言

我们开始证明\#SAT \in IP如下：

• TQBF是IP的其中一个语言

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

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

• 完备性（completeness）:如果一个字符串是在这个语言里面，检验者至少会有1/2的机率相信诚实的证明者。
• 可靠性（soundness）:如果一个字符串不在这个语言里面，检验者会有低于1/2的机率相信说谎的证明者。

虽然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内的结论，因为QIP = QIP[3]，so that more than three rounds are never necessary.

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

• 完备性：如果一个字符串在语言L里面，则诚实的验证者会有至少2/3的机率被诚实的证明者说服。

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

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

相關條目

• 黑盒
• 图灵机
• 图灵归约
• 隨機預言機

参考文献