互動式證明系統

在計算複雜性理論中，互動式證明體系（以下簡稱互動證明）是一類計算模型。像其它計算模型一樣，互動證明的目標是對一個語言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的情況下，是確定性多項式時間圖靈機），而「求解」是由一個能力更強的圖靈機完成的（在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.$

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的機率被誠實的證明者說服。

零知識證明

主條目：零知識證明

零知識證明是一種特殊的互動式證明，其中證明者知道問題的答案，他需要向驗證者證明「他知道答案」這一事實，但是要求驗證者不能獲得答案的任何資訊。

可以參考這樣一個簡單的例子。證明者和驗證者都拿到了一個數獨的題目，證明者知道一個解法，他可以採取如下這種零知識證明方法：他找出81張紙片，每一張紙片上寫上1到9的一個數字，使得正好有9份寫有從1到9的紙片。然後因為他知道答案，他可以把所有的紙片按照解法放在一個9乘9的方格內，使得滿足數獨的題目要求（每列、每行、每個九宮格都正好有1到9）。放好之後他把所有的紙片翻轉，讓沒有字的一面朝上。這樣驗證者沒辦法看到紙片上的數字。接下來，驗證者就驗證數獨的條件是否滿足。比如他選一列，這時證明者就把這一列的紙片收集起來，把順序任意打亂，然後把紙片翻過來，讓驗證者看到1到9的紙片都出現了。整個過程中驗證者都無法得知每張紙片的位置，但是卻能驗證確實是1到9都出現了。

相關條目

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