PCP Theorem Part 1: Introduction

來自專欄演算法小記27 人贊了文章

PCP Theorem的定義

我們先給出一個傳統的證明系統 (proof system)的定義：

我們有一個命題 (statement)
有一個證明者 (prover) 會給出一個證明對上面的命題證明或證否
驗證者(verifier)檢查上述證明，然後接受或拒絕這個證明

The PCP (Probabilistically Checkable Proof) Theorem:

對於任何一個在NP裡面的語言，我們都有一個如下的P.C.P. 系統

對於一個長為n的輸入
然後證明者給出一個多項式長度的證明
驗證者生成長度的隨機串，根據這個隨機串在證明裡面隨機的選個位置。這裡的是一個常數。
驗證者讀取這個位置的內容，然後進行測試來決定接受或拒絕這個證明。

這裡的驗證者要滿足如下條件:

可靠性：對於任何不滿足條件的輸入，驗證者接受它的概率不超過一半
完備性：對於如何滿足條件的輸入，驗證者一定接受它

PCP Theorem和等價

$extrm{GAP-3SAT} _{c, s}(0<sleq cleq 1)$ 的定義：給一個有m個子句(clause)的3SAT的表達式，假設我們最多能滿足其中的個句子。

如果，接受這個表達式
如果，拒絕這個表達式
如果，我們不在意這種情況，隨機選擇

定理1. PCP Theorem和 $extrm{GAP-3SAT}_{1,s} in extrm{NP-hard}$ 是等價的

證明:

假設 $extrm{GAP-3SAT}_{1,s} in extrm{NP-hard}$ 。我們這裡會證明3COLOR有P.C.P.系統。假設輸入是一個有個點的圖G。那麼驗證者首先把這個輸入歸於到一個有m個子句的 $extrm{GAP-3SAT}_{1,s}$ 表達式。這個時候證明者會被要求給出一個的賦值。然後此時證明者，只需要隨機選擇一個子句，獲得對應的三個布爾變數的賦值就好了。這個時候顯然。

可靠性 (Soundness)：如果G不能被三染色的話，那麼我們有滿足的子句小於。那麼我們隨機選擇的子句不滿足的概率是。如果這個時候 $s>frac{1}{2}$ 的話，我們重複次就好了。

完備性 (Completeness)：如果G可以被三染色的話，那麼一定可以全部被滿足。所以我們接受的概率是1。

假設我們有PCP theorem，這個時候我們把3COLOR規約到 $extrm{GAP-3SAT}_{1,s}$ 來證明 $extrm{GAP-3SAT}_{1,s}$ 是NP-hard的。首先我們有PCP theorem，那麼我們可以得到一個多項式長度的證明，在這裡我們會認為證明是對於一個3SAT表達式的賦值。然後，我們用長度的隨機串生成 $2^{O(log n)}= ext{poly}(n)=N$ 個隨機選擇。對於每個這樣的選擇，我們會生成個位置，然後讀取這個位置的值，把他們標作。我們定義一個布爾函數，當原有的3SAT表達式能在不改變這C個位置的值滿足時返回一，否則返回0。因為Cook-Levin Theorem，我們知道我們可以在多項式的時間內生成這個函數對應的3SAT表達式。因為只有個變數，我們不妨假設這個對應3SAT表達式有個子句。然後，我們用把這個長度為的表達式連接在一起，得到了一個有的3SAT表達式。

完備性 (Completeness)：如果原有的輸入是可以三染色的話，那麼我們一定可以得到完美的證明，或者說一個滿足所有子句的賦值。那麼我們新的3SAT表達式顯然是可以滿足所有子句的。

可靠性 (Soundness)：如果原有的輸入不是三染色的話，那麼根據PCP theorem，我們每次至少有一半的機會得到一個不可滿足的3SAT表達式。那麼這個3SAT表達式不可滿足的時候，它最多有 $K-1=K(1-frac{1}{K})$ 個可以滿足的子句。那麼對於，我們能夠同時滿足的不超過 $frac{N}{2}K(1-frac{1}{K})+frac{N}{2}K=NK(1-frac{1}{2K})=m(1-frac{1}{2K})$ 。也就是說我們能夠得到一個常數 $s=1-frac{1}{2K}$ 。