每周量子雜志都會解釋推動現代研究的最重要理念之一。本周，計算機科學特約撰稿人Ben Brubaker解釋了計算機科學的發展如何改變了數學中最古老的概念之一。

圖源：Nash Weerasekera | Quanta

作者：Ben Brubaker（量子雜志撰稿人）2025-1-6

譯者：zzllrr小樂（數學科普公眾號）2025-1-7

原則上，數學家只要坐在舒適的扶手椅上，認真思考，然后一步一步地寫出論點，就可以發現新的真理。這種設計證明的基本方法可以追溯到2000多年前（盡管扶手椅是最近添加的）。但證明不僅適用于數學家，在過去的幾十年里，理論計算機科學家已經開發出全新的方法來思考它們。

對于計算機科學家來說，證明的關鍵特性是很容易檢查結果是否有效。例如，我們經常讓計算機解決難以手動解決的問題。在這些情況下，最好有某種嚴格的保證——即一個證明——計算機的解確實是正確的。對于計算機科學家關心的許多問題來說，這是可能的，但不是全部。

在1980年代，少數計算機科學家開始想知道，如果計算機的正確性證明不必像普通數學證明那樣寫下來，情況會如何變化。也許交互式過程可以幫助他們驗證更多問題的解？這是一個吸引人的想法，植根于真正的數學家們互相說服他們的論點是有效的方式。

“你正在與你的學生互動，他們可以問你不同的問題，”去年秋天我與計算機科學家湯姆·古爾（Tom Gur）交談時說。“也許這其中有更大的力量。”

事實上，研究人員很快發現交互式證明比普通證明強大得多——它們可以驗證更難的問題的解。但交互式證明只是一個開始。從那以后的幾十年里，計算機科學家一次又一次地重新發明了證明。他們的發明對數學和計算機科學的其他分支，甚至量子物理學都產生了深遠的影響。

最新值得注意的內容

新型證明往往違背了我們對令人信服的論點應該如何運作的直覺。對于普通的數學證明，只有了解論證細節的讀者才能確定它是有效的。讀者還必須消化整個證明：一個不耐煩的讀者如果跳過一些步驟，可能會錯過論點中的缺陷。事實證明，這些性質實際上都不是必需的。在1980年代，計算機科學家發明了“零知識證明” https://www.quantamagazine.org/how-to-prove-you-know-a-secret-without-giving-it-away-20221011/ ——一種在不透露任何關于為什么是真的信息的情況下證明一個陳述是真的的方法。十年后，他們發明了“概率可檢驗證明”（PCP，probabilistically checkable proof） ，另請參閱 ，它可以說服只閱讀一小段論證的人。去年，三位計算機科學家 https://www.quantamagazine.org/computer-scientists-combine-two-beautiful-proof-methods-20241004/ 終于想出了如何將這兩種證明技術的理想版本結合起來。在我寫了一篇關于這一突破的文章一個月后，該團隊進一步推動了他們的結果。https://arxiv.org/abs/2411.07972

在計算機科學家發現交互式證明的強大功能后，他們很快就轉向了更復雜的證明程序，涉及兩個以上參與者之間的交互。事實證明，這些“多證明者交互證明” 仍然可以驗證更難的問題的解。但是，當研究人員將研究擴展到涉及多臺量子計算機的交互式證明時，他們的發現并沒有做好準備。Kevin Hartnett報告了他們在2020年令人震驚的發現 https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/ ，即這些證明可以驗證任何可以想象的計算結果。事實證明，這一發現對數學和物理學中看似無關的問題 https://www.quantamagazine.org/mathematicians-grapple-with-sudden-answer-to-connes-embedding-conjecture-20200408/ 產生了影響。

計算機科學和數學證明之間的另一個聯系對數學研究的實踐產生了更直接的影響。它被稱為Curry-Howard對應關系，是證明和計算機程序之間的精確等價物。Sheon Han在量子雜志一篇解釋文章中分解了它的工作原理 。此鏈接是“證明助手”程序 https://www.quantamagazine.org/building-the-mathematical-library-of-the-future-20201001/ 的基礎，這些程序幫助數學家驗證其證明的正確性。正如我的同事Jordana Cepelewicz在2024年3月25日所寫的那樣 https://mailchi.mp/simonsfoundation/why-classical-computers-can-still-win-quantum-contests-2492262 ，證明助手為數學家開辟了新的合作方式。他們還使沒有傳統學術背景的研究人員更容易進入該領域——我去年最喜歡的故事 https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ 記錄了一個特別鼓舞人心的例子。

網絡上的報道

Wired雜志的YouTube頻道提供了一系列精彩的視頻，研究人員在其中以五個不同的復雜程度解釋了一個概念。我真的很喜歡計算機科學家Amit Sahai用隱藏在企鵝群中的海鸚的照片向一個10歲的孩子解釋零知識證明 https://www.youtube.com/watch?v=fOGdb1CTu5c 的方式。

計算機科學家托馬斯·維迪克（Thomas Vidick）是2020年關于量子糾纏如何影響交互式證明的論文的合著者，他寫了一篇長篇博文 https://mycqstate.wordpress.com/2020/01/14/a-masters-project/ ，記錄了他14年來獲得這一里程碑式結果的旅程，該結果建立在十幾名研究人員的見解之上。

在YouTube頻道Computerphile的視頻中，計算機科學家Thorsten Altenkirch對證明助手的工作原理以及它們如何幫你避免邏輯謬誤進行了有趣的概述 https://www.youtube.com/watch?v=prYaTrZUces 。

參考資料

https://mailchi.mp/quantamagazine.org/why-colliding-particles-reveal-reality-4865899

https://www.quantamagazine.org/how-to-prove-you-know-a-secret-without-giving-it-away-20221011/

https://www.quantamagazine.org/how-computer-scientists-learned-to-reinvent-the-proof-20220523/

https://www.quantamagazine.org/computer-scientists-combine-two-beautiful-proof-methods-20241004/

https://arxiv.org/abs/2411.07972

https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/

https://www.quantamagazine.org/mathematicians-grapple-with-sudden-answer-to-connes-embedding-conjecture-20200408/

https://www.quantamagazine.org/the-deep-link-equating-math-proofs-and-computer-programs-20231011/

https://www.quantamagazine.org/building-the-mathematical-library-of-the-future-20201001/

https://mailchi.mp/simonsfoundation/why-classical-computers-can-still-win-quantum-contests-2492262

https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/

https://www.youtube.com/watch?v=fOGdb1CTu5c

https://mycqstate.wordpress.com/2020/01/14/a-masters-project/

https://www.youtube.com/watch?v=prYaTrZUces

科普薦書

【更多讀者好評數學書單推薦、數學科普作家自薦、出版社書單推薦通道已陸續打開，敬請期待】

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數學科普不迷路！