互動式證明系統

在計算複雜性理論中，互動式證明體系組成，兩者都可以看作是某類圖靈機。而它的計算過程為：給定了輸入x，透過驗證者和證明者之間交換資訊，最終，由驗證者來根據證明者給出的資訊，判斷給定的輸入是不是在語言L中。互動證明的基本假設是：證明者在計算能力上是無限的，在機率多項式時間的圖靈機。一般來說，對給定的L，我們關注的是互動證明中驗證者V這一角色，並對它加以如下的要求：如果對L，這樣的驗證者存在，那麼稱L有這樣的一個互動體系。類似對圖靈機所需的執行時間和空間等加以限制來得到語言的集合——複雜性類一樣，透過改變互動證明中，互動過程的輪數、隨機源是公開的還是驗證者所私有的，以及證明者的數目等等引數，可以得到不同能力的證明體系，並依據一個語言是不是有這樣引數的互動證明，來定義相應的語言的集合——複雜性類。依據互動證明定義的主要複雜性類有IP和AM，它們與依據圖靈機定義的經典複雜性類的關係是重要的研究課題。NP.導致互動證明的發現的第一個觀察是對NP的如下的理解：NP可以理解為解可以在多項式時間進行驗證的問題的集合，而求這個解的過程可能是較為困難的，如對NP完備問題，現今仍未有多項式時間的演算法。這樣，“驗證解”和“求解”這兩項計算任務就有了計算能力上的差異。所以可以假設“驗證解”是由驗證者完成。下面用PTM代表確定性多項式時間圖靈機。於是從NP，可以設計如下的互動證明：給定L∈NP，和x∈L，我們知道對x的一個解w，有一PTM，對輸入(x, w)，輸出“接受”當且僅當w是x的一個解。考慮一輪的，由證明者P發起的互動證明：因此，NP是包含在輪數為1、交換資訊長度為多項式的、驗證者是確定性圖靈機的證明體系中的。反過來，這樣的證明體系定義的語言容易看出也是在NP中的。這樣NP就與這樣的證明體系等價。可以證明，當驗證者是確定性圖靈機，每輪交換資訊長度為多項式的，即便將輪數擴充套件成多項式輪，所得到的互動證明仍然與NP是等價的。這樣就需要將驗證者擴充套件成隨機性圖靈機，此時就有了下面的有趣的複雜性類。梅林-亞瑟協議.保持輪數為1輪，由證明者發起，而將上面的PTM換作機率多項式時間圖靈機，可以得到複雜性類MA:驗證者是一個在機率多項式時間的圖靈機(亞瑟)，證明者給出對於問題的解之後驗證者必須在1/3的錯誤率以內決定"n"是否在這個語言之內。更正式地說：對任何語言"L", formula_1若formula_2是多項式formula_3:The second condition can alternatively be written asIP.在計算複雜性理論內，IP是由以下特定互動式證明系統所能解決的一類問題：驗證者是一個在機率多項式時間的圖靈機，雙方可以交換多項式formula_7次資訊，最後驗證者必須在1/3的錯誤率以內決定"n"是否在這個語言之內。更正式的說：對任何語言"L", formula_8若formula_9:和AM不同之處在於，它的交換資訊次數是被常數次數而非被一個多項式次數所限定。IP = PSPACE.要證明IP與PSPACE相等，我們先證明出IP是PSPACE的子集，然後證明PSPACE也是IP的子集，因此之故兩個集合相等。要證明出formula_12，我們展現出一個用多項式空間的機器可以怎樣模擬一個互動式證明系統。要證明formula_13這一件事，我們推導一個PSPACE-完全語言TQBF是在IP裡面。這兩個部份的證明均是由Sipser提出的。設"A"是IP裡的一個語言。 Now, assume that on input "w" with length "n", "A"'的檢驗者"V" exchanges exactly formula_14 messages.我們現在建立一個機器"M"來模擬"V"，並且"M"是PSPACE機器。 為了達到這個目的，我們定義"M"如下：formula_15根據formula_16的定義, we have formula_17 if formula_18 and formula_19 if formula_20.現在，我們可以定義：formula_21並且對任何formula_22 and every message history formula_23，我們歸納定義這個函式formula_24如下：formula_25where the term formula_26 is defined as follows:formula_27為了展示我們證明formula_28的方法，我們先證明一個比較弱的理論：formula_29。然後利用這個證明的概念去證明formula_30。既然TQBF formula_31 PSPACE-完全，我們可以得知若formula_30則PSPACE formula_33 IP，因此證明PSPACE formula_33 IP.我們開始證明formula_29如下：MIP.在1988年，Goldwasser et al.基於IP創造了另一個更強的互動式證明系統MIP，它包含"兩個"獨立的證明者。一旦檢驗者開始跟證明者溝通的時候，這兩位證明者就不能互相溝通。多了一個證明者讓檢驗者可以檢查第一個證明者的證明，會讓避免檢驗者被證明者欺騙的工作變得更簡單，就像犯人自白時讓他與他的同夥分開在兩個無法互相溝通的地方自白時會比較容易找出他們是否說謊一樣。事實上，這一件事的差異大到Babai, Fortnow，和Lund證明了MIP = NEXPTIME，這類問題是在"指數時間"之內以非決定性解的出來的問題，這是一個非常大的類別。此外，在MIP系統內，即使不做任何多餘的假設，所有的NP語言均有零知識證明；在IP裡面唯有假設存在單向函式才可能成立。IPP.IPP是 IP的一種變體，將原來的BPP檢驗者換成PP檢驗者。更精確的說，我們將完備性跟可靠性的條件修改如下：雖然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系統則是將證明者減弱如下：零知識證明.零知識證明是一種特殊的互動式證明，其中證明者知道問題的答案，他需要向驗證者證明“他知道答案”這一事實，但是要求驗證者不能獲得答案的任何資訊。可以參考這樣一個簡單的例子。證明者和驗證者都拿到了一個數獨的題目，證明者知道一個解法，他可以採取如下這種零知識證明方法：他找出81張紙片，每一張紙片上寫上1到9的一個數字，使得正好有9份寫有從1到9的紙片。然後因為他知道答案，他可以把所有的紙片按照解法放在一個9乘9的方格內，使得滿足數獨的題目要求。放好之後他把所有的紙片翻轉，讓沒有字的一面朝上。這樣驗證者沒辦法看到紙片上的數字。接下來，驗證者就驗證數獨的條件是否滿足。比如他選一列，這時證明者就把這一列的紙片收集起來，把順序任意打亂，然後把紙片翻過來，讓驗證者看到1到9的紙片都出現了。整個過程中驗證者都無法得知每張紙片的位置，但是卻能驗證確實是1到9都出現了。