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