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

圖源：Nash Weerasekera | Quanta

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

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

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

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

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

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

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

最新值得注意的內(nèi)容

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

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

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

網(wǎng)絡上的報道

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

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

在YouTube頻道Computerphile的視頻中，計算機科學家Thorsten Altenkirch對證明助手的工作原理以及它們?nèi)绾螏湍惚苊膺壿嬛囌`進行了有趣的概述 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

科普薦書

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

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

讓數(shù)學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

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

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數(shù)學科普不迷路！