大數據文摘授權轉載自zzllrr小樂
作者：Mordechai Rorvig
譯者：zzllrr小樂
如果有一百萬個計算機科學家一起吃飯，他們會支付巨額賬單。如果他們中有個人特別節儉並想檢查賬單是否正確，那麼這個過程會很簡單，即使很乏味：他們必須檢查賬單並將所有項加起來，一次一行，以確保總和一致。
但在 1992 年，六位計算機科學家在兩篇論文（https://ieeexplore.ieee.org/document/267823）中，證明了一條激進的捷徑是可能的。對任何長度的賬單，總有一種方法可以重新格式化，使得對其檢查只需少量查詢。更重要的是，他們發現任何計算，甚至任何數學證明都是如此，因為兩者都有自己的「收據」，即：計算機或數學家必須採取的步驟的記錄。
這種非常簡潔的格式被稱為PCP（概率可檢查證明Probabilistically Checkable Proof）。（根據 Ryan O'Donnell的說法https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf，該首字母縮略詞顯然是在警察錯誤地前往其中一位發明者 Shmuel Safra 的酒店房間突擊搜捕毒品後選擇的，當時警察試圖搜查毒品苯環己基哌啶（PhenylcyClohexyl Piperidine，也稱為 PCP，或天使塵）。
PCP 已成為理論計算機科學中一些最重要的工具。最近，它們甚至進入了實際應用，例如在加密貨幣中，它們被用於將大批量交易匯總成更易於驗證的較小形式。
斯坦福大學的Dan Boneh說：「我不知道有任何這樣的例子——或者可能只是非常罕見——這樣深層次的代數工具實際上可以實際應用。」
在創建 PCP 之前，計算機科學家已經通過類似於晚餐支票的解決方案確定了一整類問題——一旦獲得，就很容易驗證。但是對於其中許多問題，首先找到解似乎需要花費不切實際的時間。
計算機科學家將這類難以解決但容易驗證的問題命名為 NP。它為我們關心的許多實際問題以及更抽象的問題（例如尋找數學定理的證明）提供了概念性的家。證明是一步一步的食譜，可以絕對確定地建立他們的數學結論——就像逐項賬單提供欠款總額的證明一樣。證明可能很難獲得，但一旦你有了證明，它就可以直接檢查。這將證明完全歸入 NP 的範疇。
在 1980 年代，計算機科學家開始重新構想證明可能是什麼。密碼學家想知道是否有可能在不查看證明內容的情況下知道證明是真實的。他們將證明的結構分成兩部分系統，一個「驗證者」（verifier）試圖檢查一個由「證明者」（prover）提供的證明，後者以某種方式找到了證明。
1992 年的 PCP 定理表明，證明者總是有可能以新的形式對證明進行編碼，這樣無論證明的原始長度如何，都可以通過恆定數量的查詢對其進行驗證。必要的查詢數量最終減少到只有兩三個。驗證者不會完全確定地知道這是正確的，但是通過進行更多的查詢，可以穩定而直接地增加其確定性。這一結果違背了直覺。更長的證明一定需要你檢查更多的證據嗎？並不如此。
多倫多大學的Swastik Kopparty說：「難以置信的是，這樣的事情是正確的。」 「直到 PCP 定理被證明前不久，沒有人敢做出這樣的聲明。」
該定理使人們對 NP 有了新的理解，並解釋了它的一些有趣的性質。計算機科學家發現，對於一些 NP 問題，答案似乎不僅難以計算，而且也難以近似估算。PCP 定理有助於解釋原因。它說，如果找到了 NP 問題的解，它總是可以重新格式化，從而來自驗證者的大多數檢查（比如 90%）都能通過（但不是全部，因為證明仍然只是概率性的）。因此，從驗證者的角度來看，問題似乎已大致解決，準確率達到 90%。但由於 NP 問題很難解決，因此通常很難為它們找到 PCP，因此也很難找到超出某個點（例如 90%）近似正確的解。
科學家們還開始考慮 PCP 實際應用的可能性。不幸的是，90 年代的 PCP 效率極低。證明者需要數千年才能產生代表任何實際計算的 PCP。此外，任何實際的 PCP 都會很大，需要一個行星大小的硬盤。
但是到 2008 年，研究人員發現 PCP 的大小和計算量的增長速度要慢得多，這使得它們更易於駕馭。然後，在 2010 年代中期，研究人員開始構建更小的 PCP 新形式，稱為交互式預言機證明 (IOP，interactive oracle proofs)，它增加了證明者和驗證者之間的額外交互回合，在每一輪中，證明者可以產生更小更快的證明。
「通過添加交互並使用從 PCP 技術移植而來的大量相同數學，你可以獲得實用的東西，」離開以色列海法 Technion 並創辦 StarkWare 公司的計算機科學家Eli Ben-Sasson說。
在過去的十年中，計算機科學家還在加密貨幣背後的軟件中發現了 PCP（及其後代）的直接應用，這些軟件現在也引發了他們自己的有趣的理論問題。在其中一個軟件系統中，大型計算機（證明者）驗證金融交易並將驗證計算置於 PCP 中，因此較小的計算機（驗證者）可以更快地驗證交易。
但是假設證明者試圖作弊，例如，通過在 PCP 中隱藏一組虛假交易。當一個 PCP 系統（由證明者、驗證者和 PCP 組成）能夠抵禦這種欺騙時，研究人員稱它具有「可靠性」。可靠性在理論上和實際應用中都很重要，其中更好的可靠性（由某個參數量化）轉化為更快的驗證和更少的計算工作。
2020 年 5 月，Ben-Sasson、Dan Carmon、Yuval Ishai、Kopparty 和 Shubhangi Saraf 發表的一篇論文表明，現代 PCP 系統的可靠性達到了理論計算機科學的基本極限。這是以一種經典形式編碼（稱為 Reed-Solomon 編碼，RS糾錯碼）的數據的最大已知持久性，這也是一個證明或計算通過 PCP 編碼的方式。
PCP 仍然可以提高效率。最近，兩組研究人員發現了一種對大塊數據進行編碼的最佳方法，這樣只需在幾個點檢查它就可以發現整個塊是否已損壞。此方法通過提供僅依賴於幾個查詢的完整性測試來執行類似於 PCP 的操作，同時在速度和大小方面也達到了完美的效率。研究人員將其視為一種概念證明，有朝一日可能會找到完美的最佳 PCP。
「這不是一個簡單的問題，」德克薩斯大學奧斯汀分校的Dana Moshkovitz說。「[但]感覺我們應該出發去做。」
留言列表