【原】小樂數學科普：PCP定理簡史——概率可檢驗證明

譯者注：

PCP（probabilistic checkable proofs）概率可檢驗證明定理是計算復雜性理論中的重要定理之一，

PCP 定理指出  NP = PCP [O(log n ), O(1)]

是近似計算難度理論的基石，它研究了為各種優化問題設計有效近似算法的內在困難。它被Ingo Wegener描述為“自庫克定理以來復雜性理論中最重要的結果”。

本文用于輔助閱讀最近譯文《小樂數學科普：計算機科學家如何學會重新發明證明——譯自Quanta Magazine量子雜志》。

來源：華盛頓大學官網CS課程 2005-9

https://www.cs./education/courses/

https://courses.cs./courses/cse533/

（zzllrr小樂 2022-5-24）

（這是作者 Ryan O'Donnell 推斷的關于 PCP 定理歷史的簡要梳理。主要資料來源是 Babai 的文章 《電子郵件和意想不到的互動力量》（Email and the unexpected power of interaction）、Goldreich 的文章《證明系統的分類》（A taxonomy of proof systems），以及相應原始來源。可能有一些不準確和遺漏，對此我深表歉意并要求提前更正。由于此筆記是為華盛頓大學（UW）的課程準備的，因此還強調了與華盛頓大學 有關的一些細節。）

有了 Irit Dinur（2005 年 4 月）對 PCP 定理的激動人心的新證明，他的 PCP 定理課程不再需要涉及原始證明中的許多細節（如果有的話）。但是這個原始證明和導致它的七年工作形成了一段有趣的歷史，當然值得一聽。

PCP 定理的故事始于 1980 年代初在麻省理工學院，GMR（Goldwasser、Micali 和 Rackoff）的一篇論文將贏得有史以來第一個哥德爾獎：《交互式證明系統的知識復雜性》（The Knowledge Complexity of Interactive Proof Systems）。該文首次發表于 STOC '85。然而，據說它的草稿早在 82 年末就已經存在。事實上，據說它至少在 83 年的一篇論文中被引用過。故事還說，這篇論文被 FOCS '83、STOC '84 和 FOCS '84 拒絕，盡管尚不清楚這些拒絕的論文是什么形式的。

Goldwasser、Micali 和 Rackoff 實際上對證明所意味著的哲學概念很感興趣，盡管他們論文的主要動機是密碼學。該論文介紹了兩個新概念：交互式證明和零知識證明。

定義 1

在交互式證明中，具有私人投幣功能的隨機多時間驗證者與全能證明者進行交互；他們以多項式次數來回發送消息。正確的陳述應該有接受概率 1（“完整性completeness”）的證明，不正確的陳述應該被拒絕，不管證明如何，概率至少為 1/2（“可靠性”）。（實際上，GMR 最初允許 1 - 2? ? 完整性；事實證明這并不重要。）我們用 IP 表示具有交互式證明（interactive proofs）的語言類別。

這是 GMR 能考慮的最普遍的有效證明概念；他們以學生在課堂上與提供證明的講師互動的想法為模型。至于他們關于零知識證明的其他概念，我們不會在這里詳細介紹，只是要說，在傳統證明中，除了它是正確的事實之外，你還可以“學習”關于該定理的許多東西，在交互式證明除了定理為真這一事實之外，你還可以得知“零附加信息”。GMR 的主要例子是“二次非剩余”問題。通過給出模的分解作為見證，在 NP 中不難證明一個數是二次非剩余（平方非剩余）；然而，這揭示了很多信息。GMR 對這一事實給出了“零知識”證明。這當然是零知識證明的一個有趣的例子，但不是交互式證明的一個有趣的例子，因為問題已經在 NP 中了。

獨立于 GMR 并在同一個 STOC '85 上發表的是 Babai 的一篇論文，即隨機性交易群論。這篇論文后來發表在期刊上，名為 《亞瑟王-魔法師梅林游戲：隨機證明系統和復雜性等級的層次結構》（Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes），Moran 是合著者；事實上，這篇論文與 GMR 分享了有史以來的第一個哥德爾獎。Babai 曾與 Szemerédi 寫過一篇論文，其中他基于一些未經證實的群論假設，證明了某些特定的群論問題在 NP 中（例如，對于由其生成元給出的有限域上的矩陣群，它的階數至多為 k嗎？）。Babai 想要得到一個無條件的結果，所以他獨立引入了交互式證明的概念，盡管是公開的拋硬幣，并證明他的問題有常數回合的交互式證明。特別地，他給出了以下定義：

定義 2

AM[k] 是具有 k 輪的交互式證明類，其中驗證者首先發言并公開拋硬幣。（AM 代表 Arthur-Merlin，亞瑟王Arthur 是驗證者，魔法師梅林Merlin 是證明者。）

Babai還證明了：

定理 1 對于所有常數 k，AM[k] = AM[2]

如今AM[2] 類簡稱為 AM。通過這個定義，我們看到 AM[poly] 與 IP 非常相似；主要區別在于公共硬幣與私人硬幣。此后不久 Goldwasser 和 Sipser (STOC '86) 表明他們是同一類。因此，在這篇論文之后，出現了一個很好的健壯的類，稱為 IP 定義的（IP defined），它似乎捕捉到了具有有效證明的自由語言概念。

事實上，這門課很快就成為復雜性理論家感興趣的一門課，原因如下：GMR 的交互式證明是針對已經存在于 NP 中的東西。Babai 的證明是針對他懷疑在 NP 中但沒有足夠的群論來證明的東西。但是在 FOCS '86 中（實際上，這個結果在 Goldwasser-Sipser 之前就已經被知道了一些），Goldreich、Micali 和 Wigerson 表明圖的非同構性（Graph Non-Isomorphism） 問題存在于 IP 中，這是人們曾考慮很長一段時間，并試圖放入NP的一個問題。

定義 3

圖的非同構性是圖的同構性的補：給定 G? = (V?, E?) 和 G? = (V?, E?)，兩個鄰接格式的圖。它們是同構的嗎？即是否可以重命名頂點以使它們是相同的圖？

定理 2 (GMW '86) 圖的非同構性在 IP中

證明：

驗證者隨機選擇 i ∈ {1, 2}，隨機排列 Gi 的頂點，并將結果圖呈現給證明者。證明者必須猜測 i。對于完整性來說，如果圖是非同構的，那么全能的證明者當然可以識別 i。對于可靠性來說，如果圖是同構的，那么無論 i 是什么，證明者都會在圖上看到相同的概率分布；因此它所能做的就是猜測。

在此之后的一段時間內，IP 方面沒有任何重大進展，盡管交互式證明繼續受到加密社區的關注。特別是，在 STOC '88 中，為了從有關零知識證明的一些結果中刪除密碼學假設，BGKW（Michael Ben-Or、Goldwasser、Joe Kilian 和 Wigderson） 引入了多證明者的交互證明的概念：

定義 4 (BGKW '88.) MIP ：具有多個非通信證明者（Multiple, noncommunicating provers）的交互式證明（IP）類。

BGKW 的一個定理表明，具有多項式個證明者的 MIP 與具有兩個證明者的 MIP 相同。

再有一段時間，由于交互式證明的復雜性，事情停滯不前。Babai 猜想 IP = AM，事實上大多數人似乎認為 IP（甚至 MIP）只是 NP 的略微隨機的推廣。從哲學的角度來看，這似乎是非常合理的：為什么人們應該期望從有效證明概念的這種合理推廣中獲得顯著的額外力量？88 年的 Fortnow 和 Sipser 表明，有一個預言機相對于其 coNP 不在 IP 中；同年，Fortnow、Rompel 和 Sipser 將這一結果推廣到 MIP。（這篇論文還使用證明檢查對 MIP 進行了重新定義，這將在以后證明是有用的……）由于這個預言結果，任何類似 coNP ? MIP 的證明都需要復雜性理論中的一種前所未見的證明技術（特別地，是一種非相對化技術）。正如Babai后來所寫的那樣，這是一個相當大的“情感障礙”。

因此，當 1989 年 11 月 27 日，Nisan 向一些同事發送了一封電子郵件，表明（Permanent and hence）P#P ? PH （Toda早在 1989 年證明）是在 MIP中。然后Nisan到了南美度假。值得注意的是，他的論文建立在 1989 年 M. Blum 和 S. Kannan 的程序檢查、Lipton 的Permanent的隨機自還原性以及 Beaver 和 Feigenbaum 的預言和代數編碼的最新工作的基礎上。.

Nisan 的結果非常令人印象深刻，但有些人質疑 MIP 的相關性——雖然 IP 作為有效證明的概念聽起來很合理，但 MIP 貌似并不清楚。僅僅兩周后，情況發生了巨大變化。12 月 13 日，Fortnow 在芝加哥為三人小組（Karloff 和 Lund）寫作，向幾十名同事發送了一封包含 LATEX 的電子郵件，以證明 P#P（Permanent and hence）在 IP 中。這絕對是非常令人驚訝的，因為這意味著 IP 比人們意識到的要強大得多。不僅coNP在其中，整個多項式時間層級也在其中。關于 Fortnow 電子郵件收件人的旁注：華盛頓大學教授 Martin Tompa 參與其中，在我看來，威斯康星大學教授 Richard Ladner 也參與其中。正如 Babai 所寫，值得注意的是，Razborov 或其他任何來自東歐的人都沒有出現在名單上。請注意，柏林墻僅在一個月前（11 月 9 日）倒塌，而蘇聯還剩下一年半的時間。另一個旁注，關于這個結果的功勞：Lund 被列為論文的“第一作者”，違背了字母順序的標準做法，因為他顯然提出了證明中的關鍵步驟。Fortnow 后來寫道，他認為這是一個錯誤的決定。此外，Nisan 被添加為本文的合著者。因此，這個結果的通常歸功于：

定理 3 (LFKN '90) P#P ? IP

現在早就知道 IP ? PSPACE（這個結果通常歸功于 P. Feldman '86，盡管我在他關于《違背自然的游戲》“Games Against Nature”的論文中也看到它歸功于 Papadimitriou '83）；顯然，在這封電子郵件之后，試圖證明反包含的比賽開始進行。僅僅兩周后就完成了：Shamir 于 1989 年 12 月 26 日發送了一封電子郵件，介紹了一些新的聰明技術來證明：

定理 4 (Shamir '90) IP = PSPACE

（請注意，IP = PSPACE 這個結果有時記功于 LFKN+Shamir）

三周后（1990 年 1 月 17 日），Babai、Fortnow 和 Lund 不甘示弱，發出了另一封電子郵件：

定理 5 (BFL ’90) MIP = NEXP

（也就是說，任何具有指數大小證明的東西都可以用多個證明者在多時間中證明）

這一系列的工作產生了一個自然的停止點。現在，定理 IP = PSPACE 被視為復雜性理論的經典之作，并且是對可以證明有效的方法的驚人表征。MIP = NEXP 定理今天被認為有點深奧，但實際上它激發了 PCP 理論的幾乎所有未來發展。（順便說一句，通過 Babai、Fortnow、Nisan 和 Wigderson 的論文，這項工作在某種程度上也刺激了去隨機化理論的許多未來發展。）

在獲得這些結果的一年內，人們開始嘗試“縮小” NP 的結果；即，嘗試對驗證者的能力施加限制，這將重新獲得可證明的傳統概念。早期考慮的限制之一是限制驗證者對空間的使用。這方面的大部分工作是由Condon完成的，她1987 年獲得博士學位。華盛頓大學的論文因其對游戲和交互式證明的計算復雜性研究而獲得 ACM 博士論文獎。Condon 的 91 年早期 STACS 論文中的一個結果特別令人感興趣。在該文中，她表明 NP 正是一類具有交互式證明的語言，其中驗證者具有對數空間和對證明的單向讀取訪問權限。（Condon 和 Ladner 后來對該結果進行了技術改進。）主要的證明工具來自 IP = PSPACE 結果。但此外，作為推論，該論文表明矩陣的 MAX-WORD 問題（給定向量 u、v、矩陣 M?、?、Mt 和 k，最大化 < u, Mi??Mik v >）沒有常數因子逼近算法，除非 NP = P。這是有史以來第一次在交互式證明和逼近難度之間建立聯系。然而不幸的是，Condon的結果并沒有得到太多的歷史贊譽，因為空間受限的驗證者被證明不是最有效的限制途徑。為驗證者考慮的另一個限制是限制他們的時間。BFLS（Babai、Fortnow、Levin 和 Szegedy) 在 1991 年初/中期的結果表明，如果證明者被限制使用某種糾錯碼來編寫證明，那么驗證者可以使用多對數時間檢查所有 NP 語言。BFLS 將此類證明稱為“透明證明”（或有時稱為“全息證明”）。盡管亞線性時間證明檢查的可能性在哲學上非常有趣，但驗證者時間也被證明不是最有效的限制途徑。

碰巧的是，最令人興奮的結果來自同時限制驗證者使用的隨機比特數和進行證明比特訪問的數量。對于此類驗證者，讓我們先定義 Arora-Safra '92，盡管該定義的重要性在較早的論文 Feige-Goldwasser-Lovász-Safra-Szegedy '91 (FGLSS) 中首次闡明：

定義 5

PCP[r(n), q(n)] 是可使用 PCP 系統證明的語言類別，該系統使用 O(r(n)) 位隨機性，在證明中查詢 O(q(n)) 位，并且具有完整性 1，可靠性 1/2。

有了這個定義，可以看出 BFL 的 MIP = NEXP 結果等價于 NEXP ? PCP[poly, poly]。此外，如果你以正確的方式查看 多對數（polylog） 時間驗證器上的 BFLS 結果，它可以被視為顯示 NP ? PCP[polylog, polylog]。Feige、Goldwasser、Lovász 和 Safra（在普林斯頓大學）顯然獨立地（稍晚一點）證明了后一個結果。后來 Szegedy 加入了這個團隊，他們發布了一個改進的結果，以及一個讓每個人都感到驚訝的引人注目的應用，并在接下來的幾年里點燃了 PCP 研究：

定理 6 (FGLSS, FOCS '91) NP ? PCP(f(n), f(n))，其中 f(n) = log n · log log n

此外，作為一個相當直接的結果，不可能將 MAX-CLIQUE 逼近在任何常數范圍內的因子，除非 NP ? DTIME (n^( log log n))。

從這個結果可以看出 NP ? PCP[log n, log n] 必須為真；此外，現在有巨大的額外動力來證明它并改進這些 PCP 結果，因為它們對近似團的難度產生了影響。這一結果在 1992 年初（在 Nisan 的電子郵件之后兩年多一點）被伯克利的 Arora 和 Safra 在一篇介紹了許多技術發展的論文中得到了證明，其中包括首字母縮略詞“PCP”和 PCP[r(n), q(n)] 符號前面提到過。首字母 PCP 似乎是由于 Safra 而這些伯克利的作者肯定不會忘記 PCP 也是致幻劑的名稱。這個名字顯然是出于某種原因，在加利福尼亞某個地方的一次會議上發生了一起事件，警察來到了 Safra 住的會議酒店房間，想要突擊搜查毒品（PCP？）（而不是針對 Safra ——他們走錯了房間！） .

定理 7 (AS '92) NP ? PCP[log n, log n]

事實上，NP ? PCP[log n,(log n^{.5+?}]。

所以事實上，查詢可以是次對數的。事實上，一份歸因于 Arora、Motwani、Safra、Sudan 和 Szegedy 的未發表（未成文？）手稿注意到，基本上相同的證明得到的查詢是 O((log log n)2 )。Muli然后去了以色列過夏天，我想；不久之后公布了最終的改進。

定理 8 (Arora-Lund-Motwani-Sudan-Szegedy '92) NP ? PCP[log n, 1] 

盡管從未明確計算過，但據傳使用的證明查詢數量約為 10?

這個結果現在被稱為“PCP 定理”，傳統上歸功于 Arora-Safra '92 和 ALMSS '92。ALMSS 的改進融合了來自 Lapidot-Shamir '91、Feige-Lovász '92 和 Blum-Luby-Rubinfeld '90 的想法。AS 和 ALMSS 都出現在 1992 年的 FOCS 中——他們與 Nisan、Szemerédi 和 Wigderson 的一篇名為 O(log1.?n) 空間中的無向連通性的論文分享了一次會議——盡管結果的消息在 1992 年春天廣泛傳播，在 FOCS 之前的六個月，也就是 4 月 7 日，結果由 Gina Kolata 在《紐約時報》的科學版塊《長數學證明的新捷徑》（“New Short Cut Found for Long Math Proofs”）撰寫，并在一周后公布將在 STOC '92 上對結果進行非正式的介紹。（此公告在下面逐字復制，以表明 STOC 和 FOCS 顯然曾經是多么有趣。STOC 愚蠢？萊佛士？海上皮劃艇？本土故事、儀式和舞蹈？裸體蹦極？！）

盡管隨后對各種性質的 PCP 定理進行了許多改進，但其結果被認為是復雜性理論的頂峰和皇冠上的明珠。FGLSS '91、AS '92 和 ALMSS '92 共同分享了 2001 年的哥德爾獎。