互動式證明系統

在計算複雜性理論中，**交互式證明體系**（下簡稱交互證明）是一類計算模型。像其它計算模型一樣，我們的目標是對一個語言 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 發起的交互證明：

* 證明過程：
  1. V 和 P 商量好解的長度 l，且 l 是輸入的多項式；
  2. V 和 P 接到輸入 x；
  3. P 將解 w 送給 V。不論 P 送多少字符，V 只截取前 l 個；
  4. 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|$ : 

* if _x_ is in _L_, then $\exists z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\geq 2/3,$
* if _x_ is not in _L_, then $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=0)\geq 2/3.$

The second condition can alternatively be written as

* if _x_ is not in _L_, then $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\leq 1/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]\geq {\frac {2}{3}}$
* $w\not \in L\Rightarrow \Pr[V\leftrightarrow Q{\text{ accept }}w]\leq {\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** 里的一個語言。 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$ 如下：

* * **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 都出現了。

## 相關條目

* 黑盒
* 圖靈機
* 圖靈歸約
* 隨機預言機

## 參考文獻