查看“︁交互式证明系统”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
{{Copy edit|time=2021-11-17T21:48:48+00:00}}
在[[计算复杂性理论]]中，'''交互式证明体系'''（以下简称交互证明）是一类计算模型。像其它计算模型一样，交互证明的目标是对一个[[形式化语言|语言]]L，和一个给定的输入x，判断x是否在L中。交互证明由两个实体：验证者（verifier）和证明者（prover）组成，两者都可以看作是某类[[图灵机]]。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。

交互证明的基本假设是：证明者在计算能力上是无限的，在概率[[多项式时间]]（[[BPP (複雜度)]]）的图灵机。一般来说，对给定的L，我们关注的是交互证明中验证者V这一角色，并对它加以如下的要求：
* '''[[完备性]]'''（completeness）：如果x&isin;L，那么存在诚实的证明者P，使得V与P的交互之后，输出“x&isin;L”；
* '''[[健全性|可靠性]]'''（soundness）：如果x&notin;L，那么对任意的证明者P，V与P交互之后，输出“x&isin;L”的概率很小（可以认为小于某一常数）。
如果对L，这样的验证者存在，那么称L有这样的一个交互体系。

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

== NP ==
{{main|NP (复杂性类)}}

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

于是从NP，可以设计如下的交互证明：给定L&isin;NP，和x&isin;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&isin;L，当且仅当有解w，使得M(x,w)接受。所以一个好的证明者将利用它无限的计算能力得到w，故V会接受；
* 可靠性：同样由L的性质，当x&notin;L，不可能有解w，使得M(x,w)接受。所以一个坏的证明者将无法使V接受不在L中的x。

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

== 梅林-亚瑟协议（MA） ==

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

对任何语言''L'', <math>L \in MA</math>若<math>\exists P, Q</math>是多项式<math>| \forall M, M \in PTM| \forall x, n = |x|</math>: 

*if ''x'' is in ''L'', then <math>\exists z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\ge2/3,</math>
*if ''x'' is not in ''L'', then <math>\forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=0)\ge2/3.</math>

The second condition can alternatively be written as
*if ''x'' is not in ''L'', then <math>\forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\le1/3.</math>

== 亚瑟-梅林协议（AM） ==
{{Empty section}}

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

对任何语言''L'', <math>L \in IP</math>若<math>\exists V, P | \forall Q, w</math>: 

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

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

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

* '''IP是PSPACE的子集'''
设''A''是'''IP'''里的一个语言。  Now, assume that on input ''w'' with length ''n'', ''A''<nowiki>'</nowiki>的检验者''V'' exchanges exactly <math>p=p(n)</math> messages.我们现在建立一个机器''M''来模拟''V''，并且''M''是'''PSPACE'''机器。  为了达到这个目的，我们定义''M''如下：

: <math>\Pr[V\text{ accepts }w] = \max_P \Pr[V \leftrightarrow P\text{ accepts } w]</math>

根据<math>\text{IP}</math>的定义, we have <math>\Pr[V\text{ accepts }w] \ge \frac{2}{3}</math> if <math>w \in A</math> and <math>\Pr[V\text{ accepts }w] \le \frac{1}{3}</math> if <math>w \not \in A</math>. 

现在，我们可以定义：

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

并且对任何<math>0 \leq j \leq p</math> and every message history <math>M_j</math>，我们归纳定义这个函数<math>N_{M_j}</math>如下：

: <math>
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 < p\text{ and }j\text{ is odd} \\
  \text{wt-avg}_{m_{j+1}} N_{M_{j+1}}: j < p\text{ and }j\text{ is even} \\
\end{cases}
</math>

where the term <math>\text{wt-avg}_{m_{j+1}}N_{M_{j+1}}</math> is defined as follows:

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

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

* '''#SAT是IP的其中一个语言'''
我们开始证明<math>\#SAT \in IP</math>如下：

* '''TQBF是IP的其中一个语言'''

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

== IPP ==
'''IPP'''（''unbounded IP''）是 '''IP'''的一种变体，将原来的'''[[BPP (複雜度)|BPP]]'''检验者换成'''[[PP (complexity)|PP]]'''检验者。更精确的说，我们将完备性跟可靠性的条件修改如下：

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

虽然'''IPP'''仍旧与'''PSPACE'''相等，但是'''IPP'''协议系统在涉及[[启示图灵机]]的情况下与'''IP'''的状况差异颇大：对所有的启示图灵机'''IPP'''='''PSPACE'''，但是几乎对所有的启示图灵机，'''IP''' ≠ '''PSPACE'''。<ref>R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, and P. Rohatgi. [http://citeseer.ist.psu.edu/chang97random.html The random oracle hypothesis is false] {{Wayback|url=http://citeseer.ist.psu.edu/chang97random.html |date=20080416153753 }}. ''Journal of Computer and System Sciences'', 49 (1):24-39. 1994.</ref>

== QIP ==
'''QIP'''是将'''IP'''的'''[[BPP (複雜度)|BPP]]'''检验者换成一个'''[[BQP]]'''检验者所产生的变体，说更明白些，'''BQP'''是可以用[[量子计算机]]在多项式时间内解决的问题类别。并且，这一些讯息是用[[量子位]]所表示的。<ref>J. Watrous. [http://citeseer.ist.psu.edu/watrous99pspace.html PSPACE has constant-round quantum interactive proof systems] {{Wayback|url=http://citeseer.ist.psu.edu/watrous99pspace.html |date=20080416163246 }}. ''Proceedings of IEEE FOCS'99'', pp. 112-119. 1999.</ref>在2009年, Jain, Ji, Upadhyay，和Watrous证明了'''QIP'''也与'''PSPACE'''相等，<ref>{{cite arxiv|eprint=0907.4737|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4=John Watrous|title=QIP = PSPACE|class=quant-ph|year=2009}}</ref>总结起以上Kitaev和Watrous的理论，我们得到'''QIP'''包含在'''[[EXPTIME (复杂度)|EXPTIME]]'''内的结论，因为'''QIP''' = '''QIP'''[3]，so that more than three rounds are never necessary.<ref>A. Kitaev and J. Watrous. [http://www.cpsc.ucalgary.ca/~jwatrous/papers/qip2.ps Parallelization, amplification, and exponential time simulation of quantum interactive proof systems]{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}. ''Proceedings of ACM STOC'2000'', pp. 608-617. 2000. </ref>

== compIP ==
'''IPP'''跟'''QIP'''都是给予检验者更多的能力，但是一个'''compIP'''系统（''competitive IP proof system''）则是将证明者减弱如下：
* '''完备性'''：如果一个字符串在语言L里面，则诚实的验证者会有至少2/3的机率被诚实的证明者说服。

== PCP ==
{{Empty section}}

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

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

== 相關條目 ==
* [[黑盒]]
* [[图灵机]]
* [[图灵归约]]
* [[隨機預言機]]

== 参考文献 ==
{{Reflist|30em}}

{{-}}
{{复杂度类}}

[[Category:计算复杂性理论]]
[[Category:機率複雜度類]]
[[Category:包含证明的条目]]