在計算複雜性理論中，互動式證明體系（下簡稱互動證明）是一類計算模型。
基本介紹
- 中文名：互動式證明系統
- 簡稱：互動證明
- 類別：計算模型
- 特點：完備性 可靠性
- 領域：計算複雜性理論
- 學科：計算機
簡介,NP,MIP,IPP,QIP,compIP,零知識證明,
簡介
在計算複雜性理論中，像其它計算模型一樣，我們的目標是對一個語言L，和一個給定的輸入x，判斷x是否在L中。互動式證明體系由兩個實體：驗證者（verifier）和證明者（prover）組成，兩者都可以看作是某類圖靈機。而它的計算過程為：給定了輸入x，通過驗證者和證明者之間交換信息，最終，由驗證者來根據證明者給出的信息，判斷給定的輸入是不是在語言L中。
互動證明的基本假設是：證明者在計算能力上是無限的，而驗證者一般設為多項式時間的、可使用隨機源的圖靈機。一般來說，對給定的L，我們關注的是互動證明中驗證者V這一角色，並對它加以如下的要求：
完備性（completeness）：如果x∈L，那么存在誠實的證明者P，使得V與P的互動之後，輸出“x∈L”；
可靠性（soundness）：如果x∉L，那么對任意的證明者P，V與P互動之後，輸出“x∈L”的機率很小（可以認為小於某一常數）。
如果對L，這樣的驗證者存在，那么我們說L有這樣的一個互動體系。
類似對圖靈機所需的運行時間和空間等加以限制來得到語言的集合——複雜性類一樣，通過改變互動證明中，互動過程的輪數、隨機源是公開的還是驗證者所私有的，以及證明者的數目等等參數，我們可以得到不同能力的證明體系，並依據一個語言是不是有這樣參數的互動證明，來定義相應的語言的集合——複雜性類。依據互動證明定義的主要複雜性類有NP和AM，它們與依據圖靈機定義的經典複雜性類的關係是重要的研究課題。
NP
導致互動證明的發現的第一個觀察是對NP的如下的理解：我們知道NP可以理解為解可以在多項式時間進行驗證的問題的集合，而求這個解的過程可能是較為困難的，如對NP完備問題，現今仍未有多項式時間的算法。這樣，“驗證解”和“求解”這兩項計算任務就有了計算能力上的差異。所以我們可以假設“驗證解”是由驗證者完成（在NP的情況下，是確定性多項式時間圖靈機），而“求解”是由一個能力更強的圖靈機完成的（在NP的情況下，可以假設是確定性指數時間圖靈機）。下面我們用PTM代表確定性多項式時間圖靈機。
於是從NP我們可以設計如下的互動證明：給定L∈NP，和x∈L，我們知道對x的一個解w，有一PTM，對輸入(x, w)，輸出“接受”若且唯若w是x的一個解。我們考慮一輪的，由證明者P發起的互動證明：
- 證明過程：
- V和P商量好解的長度l，且l是輸入的多項式；
- V和P接到輸入x；
- P將解w送給V。不論P送多少字元，V只截取前l個；
- 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是等價的。這樣就需要將驗證者擴展成隨機性圖靈機，此時我們就有了下面的有趣的複雜性類。
MIP
在1988年，Goldwasser et al.基於IP創造了另一個更強的互動式證明系統MIP，它包含兩個獨立的證明者。一旦檢驗者開始跟證明者溝通的時候，這兩位證明者就不能互相溝通。多了一個證明者讓檢驗者可以檢查第一個證明者的證明，會讓避免檢驗者被證明者欺騙的工作變得更簡單，就像犯人自白時讓他與他的同夥分開在兩個無法互相溝通的地方自白時會比較容易找出他們是否說謊一樣。事實上，這一件事的差異大到Babai, Fortnow，和Lund證明了MIP=NEXPTIME，這類問題是在指數時間之內以非決定性解的出來的問題，這是一個非常大的類別。此外，在MIP系統內，即使不做任何多餘的假設，所有的NP語言均有零知識證明；在IP裡面唯有假設存在單向函式才可能成立。
IPP
- 完備性（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內的結論。
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都出現了。
