User:Edisonabcd/沙盒/IP

在计算复杂性理论内，IP是由交互式证明系统所能解决的一类问题。交互式证明系统的概念最早是由Shafi Goldwasser，Silvio Micali，和Charles Rackoff在1985年提出的。一个交互式证明系统包含两个参与者，一个证明者（prover），P，它展示出一个长度为n的输入字符串x是否在语言L之内的证明，和一个验证者（verifier），V，检查这个证明是否正确。这里假设证明者有无限的计算能力跟容量，而验证者是一个多项式时间且可以访问随机数的机器。双方可以交换多项式$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]\geq {\frac {2}{3}}$
• $w\not \in L\Rightarrow \Pr[V\leftrightarrow Q{\text{ accept }}w]\leq {\frac {1}{3}}$。

由Laszlo Babai提出的阿瑟默林协议与其相当相似，不过它的交换信息次数是被常数次数而非被一个多项式次数所限定。

在后面的部份我们将证明${\text{IP}}={\text{PSPACE}}$，一个在计算复杂性理论中非常重要的证明。

证明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里的一个语言。 Now, assume that on input w with length n, A'的检验者V exchanges exactly $p=p(n)$ messages.我们现在建立一个机器M来模拟V，并且M是PSPACE机器。 为了达到这个目的，我们定义M如下：

$\Pr[V{\text{ accepts }}w]=\max _{P}\Pr[V\leftrightarrow P{\text{ accepts }}w]$

根据${\text{IP}}$的定义, we have $\Pr[V{\text{ accepts }}w]\geq {\frac {2}{3}}$ if $w\in A$ and $\Pr[V{\text{ accepts }}w]\leq {\frac {1}{3}}$ if $w\not \in A$.

现在，我们可以定义：

$\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$ and every message history $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<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}}$

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

${\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$如下：

变体

现在已知有许多IP的变体，它们一般是稍稍改变了交互式证明系统的定义产生出来的。我们在下面列出几个比较为人所知的变体：

MIP

主条目：交互式证明系统 § 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的机率被诚实的证明者说服。

参考数据

• Babai, L. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation . ACM, New York, 1985, pp. 421–429.
• Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge complexity of interactive proof-systems. Proceedings of 17th ACM Symposium on the Theory of Computation, Providence, Rhode Island. 1985, pp. 291–304. Extended abstract
• Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Proceedings of the 18th Annual ACM Symposium on Theory of Computation. ACM, New York, 1986, pp. 59–68.
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [1]
• Lund, C., Fortnow, L.. Karloff, H., Nisan, N. Algebraic methods for interactive proof systems. In Proceedings of 31st Symposium on the Foundations of Computer Science. IEEE, New York, 1990, pp. 2–90.
• Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
• Alexander Shen. IP=PSpace: Simplified Proof. J.ACM, v. 39 (4), pp. 878–880, 1992.
• Sipser, Michael. "Introduction to the Theory of Computation", Boston, 1997, pg. 392–399.
• Complexity Zoo: IP, MIP, IPP, QIP, QIP (2), compIP, frIP