IP (複雜度)

本条目“IP (複雜度)”在中文维基百科已被删除（其它版本），这是一个删除前的存档副本。 AT删除了IP (複雜度)，理由是： 存废讨论通过：[[Wikipedia:頁面存廢討論/記錄/2016/08/22]] using [[WP:TWINKLE|TW]]。 这个理由未必准确 (为什么？) 本条目共存留2442天： 创建于：2009-12-29 删除于：2016-09-05 贡献者：11人 编辑：27次 浏览：814次（不包括bot和爬虫） 存留期间浏览量统计
请阅读免责声明。删除百科只是中文维基百科被删除条目的存档。		建议删除本条目

本条目在2011-02-05T12:48:05+00:00被认为需要专家关注。

在計算複雜性理論內，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