IP (複雜度)

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

計算複雜性理論內, IP是由交互式證明系統所能解決的一類問題。交互式證明系統的概念最早是由Shafi GoldwasserSilvio 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] \ge \frac{2}{3}
  • w \not \in L \Rightarrow \Pr[V \leftrightarrow Q\text{ accept }w] \le \frac{1}{3}.

Laszlo Babai提出的亞瑟梅林協定與其相當相似,不過它的交換資訊次數是被常數次數而非被一個多項式次數所限定。

在後面的部份我們將證明\text{IP} = \text{PSPACE},一個在計算複雜性理論中非常重要的證明。

證明IP = PSPACE[编辑]

要證明IPPSPACE相等,我們先證明出IPPSPACE的子集,然後證明PSPACE也是IP的子集,因此之故兩個集合相等。要證明出\text{IP} \subseteq \text{PSPACE},我們展現出一個用多項式空間的機器可以怎樣模擬一個交互式證明系統。 要證明\text{PSPACE} \subseteq \text{IP}這一件事,我們推導一個PSPACE-完全 語言 TQBF 是在IP裡面。 這兩個部份的證明均是由Sipser提出的。

IP是PSPACE的子集[编辑]

AIP裡的一個語言。 Now, assume that on input w with length n, A'的檢驗者 V exchanges exactly p=p(n) messages. 我們現在建立一個機器M來模擬V,並且MPSPACE機器。 為了達到這個目的,我們定義M如下:

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

根據\text{IP}的定義, we have \Pr[V\text{ accepts }w] \ge \frac{2}{3} if w \in A and \Pr[V\text{ accepts }w] \le \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如下:

TQBF是IP的其中一個語言[编辑]

變體[编辑]

現在已知有許多 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, 但是 幾乎對所有的啟示圖靈機,IPPSPACE[1]

QIP[编辑]

QIP是將IPBPP 檢驗者換成一個BQP檢驗者所產生的變體, 說更明白些,BQP是可以用量子電腦在多項式時間內解決的問題類別。並且,這一些訊息是用量子位元所表示的。[2] 在2009年, Jain, Ji, Upadhyay, 和 Watrous 證明了QIP也與PSPACE相等,[3] 總結起以上Kitaev和Watrous的理論,我們得到QIP 包含在EXPTIME內的結論,因為 QIP = QIP[3],so that more than three rounds are never necessary.[4]

compIP[编辑]

IPPQIP都是給予檢驗者更多的能力,但是一個compIP系統(competitive IP proof system)則是將證明者減弱如下:

  • 完備性: 如果一個字串在語言L裡面,則誠實的驗證者會有至少2/3的機率被誠實的證明者說服。

筆記[编辑]

  1. ^ R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, and P. Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39. 1994.
  2. ^ J. Watrous. PSPACE has constant-round quantum interactive proof systems. Proceedings of IEEE FOCS'99, pp. 112-119. 1999.
  3. ^ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous. QIP = PSPACE. arXiv:0907.4737 [quant-ph]. 2009. 
  4. ^ A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Proceedings of ACM STOC'2000, pp. 608-617. 2000.

參考資料[编辑]