交互式證明系統(tǒng)

交互式證明系統(tǒng)計(jì)算機(jī)學(xué)術(shù)語(yǔ)01簡(jiǎn)介MIPNPIPP目錄03020405QIP零知識(shí)證明compIP目錄0706基本信息在計(jì)算復(fù)雜性理論中，交互式證明體系（下簡(jiǎn)稱交互證明）是一類計(jì)算模型。簡(jiǎn)介簡(jiǎn)介在計(jì)算復(fù)雜性理論中，像其它計(jì)算模型一樣，我們的目標(biāo)是對(duì)一個(gè)語(yǔ)言L，和一個(gè)給定的輸入x，判斷x是否在L中。交互式證明體系由兩個(gè)實(shí)體：驗(yàn)證者（verifier）和證明者（prover）組成，兩者都可以看作是某類圖靈機(jī)。而它的計(jì)算過(guò)程為：給定了輸入x，通過(guò)驗(yàn)證者和證明者之間交換信息，最終，由驗(yàn)證者來(lái)根據(jù)證明者給出的信息，判斷給定的輸入是不是在語(yǔ)言L中。交互證明的基本假設(shè)是：證明者在計(jì)算能力上是無(wú)限的，而驗(yàn)證者一般設(shè)為多項(xiàng)式時(shí)間的、可使用隨機(jī)源的圖靈機(jī)。一般來(lái)說(shuō)，對(duì)給定的L，我們的是交互證明中驗(yàn)證者V這一角色，并對(duì)它加以如下的要求：完備性（completeness）：如果x∈L，那么存在誠(chéng)實(shí)的證明者P，使得V與P的交互之后，輸出“x∈L”；可靠性（soundness）：如果x?L，那么對(duì)任意的證明者P，V與P交互之后，輸出“x∈L”的概率很?。梢哉J(rèn)為小于某一常數(shù)）。如果對(duì)L，這樣的驗(yàn)證者存在，那么我們說(shuō)L有這樣的一個(gè)交互體系。類似對(duì)圖靈機(jī)所需的運(yùn)行時(shí)間和空間等加以限制來(lái)得到語(yǔ)言的集合——復(fù)雜性類一樣，通過(guò)改變交互證明中，交互過(guò)程的輪數(shù)、隨機(jī)源是公開的還是驗(yàn)證者所私有的，以及證明者的數(shù)目等等參數(shù)，我們可以得到不同能力的證明體系，并依據(jù)一個(gè)語(yǔ)言是不是有這樣參數(shù)的交互證明，來(lái)定義相應(yīng)的語(yǔ)言的集合——復(fù)雜性類。NPNP導(dǎo)致交互證明的發(fā)現(xiàn)的第一個(gè)觀察是對(duì)NP的如下的理解：我們知道NP可以理解為解可以在多項(xiàng)式時(shí)間進(jìn)行驗(yàn)證的問(wèn)題的集合，而求這個(gè)解的過(guò)程可能是較為困難的，如對(duì)NP完備問(wèn)題，現(xiàn)今仍未有多項(xiàng)式時(shí)間的算法。這樣，“驗(yàn)證解”和“求解”這兩項(xiàng)計(jì)算任務(wù)就有了計(jì)算能力上的差異。所以我們可以假設(shè)“驗(yàn)證解”是由驗(yàn)證者完成（在NP的情況下，是確定性多項(xiàng)式時(shí)間圖靈機(jī)），而“求解”是由一個(gè)能力更強(qiáng)的圖靈機(jī)完成的（在NP的情況下，可以假設(shè)是確定性指數(shù)時(shí)間圖靈機(jī)）。下面我們用PTM代表確定性多項(xiàng)式時(shí)間圖靈機(jī)。于是從NP我們可以設(shè)計(jì)如下的交互證明：給定L∈NP，和x∈L，我們知道對(duì)x的一個(gè)解w，有一PTM，對(duì)輸入(x,w)，輸出“接受”當(dāng)且僅當(dāng)w是x的一個(gè)解。我們考慮一輪的，由證明者P發(fā)起的交互證明：于是我們知道，NP是包含在輪數(shù)為1，交換信息長(zhǎng)度為多項(xiàng)式的，驗(yàn)證者是確定性圖靈機(jī)的證明體系中的。反過(guò)來(lái)，這樣的證明體系定義的語(yǔ)言容易看出也是在NP中的。這樣NP就與這樣的證明體系等價(jià)?？梢宰C明，當(dāng)驗(yàn)證者是確定性圖靈機(jī)，每輪交換信息長(zhǎng)度為多項(xiàng)式的，即便將輪數(shù)擴(kuò)展成多項(xiàng)式輪，所得到的交互證明仍然與NP是等價(jià)的。這樣就需要將驗(yàn)證者擴(kuò)展成隨機(jī)性圖靈機(jī)，此時(shí)我們就有了下面的有趣的復(fù)雜性類。MIPMIP在1988年，Goldwasseretal.基于IP創(chuàng)造了另一個(gè)更強(qiáng)的交互式證明系統(tǒng)MIP，它包含兩個(gè)獨(dú)立的證明者。一旦檢驗(yàn)者開始跟證明者溝通的時(shí)候，這兩位證明者就不能互相溝通。多了一個(gè)證明者讓檢驗(yàn)者可以檢查第一個(gè)證明者的證明，會(huì)讓避免檢驗(yàn)者被證明者欺騙的工作變得更簡(jiǎn)單，就像犯人自白時(shí)讓他與他的同伙分開在兩個(gè)無(wú)法互相溝通的地方自白時(shí)會(huì)比較容易找出他們是否說(shuō)謊一樣。事實(shí)上，這一件事的差異大到Babai,Fortnow，和Lund證明了MIP=NEXPTIME，這類問(wèn)題是在指數(shù)時(shí)間之內(nèi)以非決定性解的出來(lái)的問(wèn)題，這是一個(gè)非常大的類別。此外，在MIP系統(tǒng)內(nèi)，即使不做任何多余的假設(shè)，所有的NP語(yǔ)言均有零知識(shí)證明；在IP里面唯有假設(shè)存在單向函式才可能成立。IPPIPPIPP（unboundedIP）是IP的一種變體，將原來(lái)的BPP檢驗(yàn)者換成PP檢驗(yàn)者。更精確的說(shuō)，我們將完備性跟可靠性的條件修改如下：雖然IPP仍舊與PSPACE相等，但是IPP協(xié)議系統(tǒng)在涉及啟示圖靈機(jī)的情況下與IP的狀況差異頗大：對(duì)所有的啟示圖靈機(jī)IPP=PSPACE，但是幾乎對(duì)所有的啟示圖靈機(jī)，IP≠PSPACE。

QIPQIPQIP是將IP的BPP檢驗(yàn)者換成一個(gè)BQP檢驗(yàn)者所產(chǎn)生的變體，說(shuō)更明白些，BQP是可以用量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題類別。并且，這一些訊息是用量子位所表示的。在2009年,Jain,Ji,Upadhyay，和Watrous證明了QIP也與PSPACE相等，總結(jié)起以上Kitaev和Watrous的理論，我們得到QIP包含在EXPTIME內(nèi)的結(jié)論。

compIPcompIPIPP跟QIP都是給予檢驗(yàn)者更多的能力，但是一個(gè)compIP系統(tǒng)（competitiveIPproofsystem）則是將證明者減弱如下：零知識(shí)證明零知識(shí)證明零知識(shí)證明是一種特殊的交互式證明，其中證明者知道問(wèn)題的答案，他需要向驗(yàn)證者證明“他知道答案”這一事實(shí)，但是要求驗(yàn)證者不能獲得答案的任何信息?？梢詤⒖歼@樣一個(gè)簡(jiǎn)單的例子。證明者和驗(yàn)證者都拿到了一個(gè)數(shù)獨(dú)的題目，證明者知道一個(gè)解法，他可以采取如下這種零知識(shí)證明方法：他找出81張紙片，每一張紙片上寫上1到9的一個(gè)數(shù)字，使得正好有9份寫有從1到9的紙片。然后因?yàn)樗来鸢福梢园阉械募埰凑战夥ǚ旁谝粋€(gè)9乘9的方格內(nèi)，使得滿足數(shù)獨(dú)的題目要求（每列、每行、每個(gè)九宮格都正好有1到9）。放好之后他把所有的紙片翻轉(zhuǎn)，讓沒(méi)有字的一面朝上。這樣驗(yàn)證者沒(méi)辦法看到紙片上的數(shù)字。接下