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

圖源：Nash Weerasekera | Quanta

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

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

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

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

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

“你正在與你的學(xué)生互動(dòng)，他們可以問你不同的問題，”去年秋天我與計(jì)算機(jī)科學(xué)家湯姆·古爾（Tom Gur）交談時(shí)說?！耙苍S這其中有更大的力量。”

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

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

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

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

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

網(wǎng)絡(luò)上的報(bào)道

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

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

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

科普薦書

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

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

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評(píng)論、點(diǎn)贊、在看、在聽

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

查看原始文章出處

點(diǎn)擊zzllrr小樂

公眾號(hào)主頁

右上角

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