★置頂zzllrr小樂公眾號（主頁右上角）數(shù)學(xué)科普不迷路！

研究人員運用元數(shù)學(xué)方法證明，某些表面上看似不同的定理，實際上在邏輯上是等價的。

在反向數(shù)學(xué)領(lǐng)域中，研究人員會用他們想要證明的定理，去替換數(shù)學(xué)系統(tǒng)的基礎(chǔ) —— 公理。

圖源：Son of Alan for Quanta Magazine

作者：Ben Brubaker（量子雜志特約記者）2025-12-1

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2025-12-13

面對難題時，計算機(jī)科學(xué)家們似乎陷入了困境。例如，那個著名的TSP“旅行商問題”—— 尋找一條能恰好經(jīng)過地圖上所有城市一次的最短往返路線。在城市數(shù)量眾多的地圖上，所有已知的求解方法都異常緩慢，研究人員懷疑不存在更高效的解法，卻無人能證明這一點。

五十多年來， https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/ 計算復(fù)雜性理論領(lǐng)域的研究人員一直試圖將 “旅行商問題很難” 這類直覺性表述轉(zhuǎn)化為確鑿的數(shù)學(xué)定理，但收效甚微。如今，他們越來越多地在探尋一個相關(guān)且更模糊的問題的嚴(yán)謹(jǐn)答案：為何他們的證明屢屢受挫？

這項將數(shù)學(xué)證明過程本身作為數(shù)學(xué)分析對象的研究，隸屬于一個著名的高深領(lǐng)域 ——元數(shù)學(xué)。元數(shù)學(xué)學(xué)者常常審視作為所有證明起點的基本假設(shè)（即公理），他們會更換初始公理，進(jìn)而探索這些變化對可證明定理的影響。

當(dāng)研究人員運用元數(shù)學(xué)研究復(fù)雜性理論時，他們試圖勾勒出不同公理集在計算難度方面能證明什么、不能證明什么。他們希望通過這種方式，弄明白為何在證明問題難度的過程中始終未能取得突破。

去年發(fā)表的一篇論文中 https://eccc.weizmann.ac.il/report/2024/060/ ，三位研究人員針對這一挑戰(zhàn)提出了一種新方法。他們顛覆了數(shù)學(xué)家們沿用數(shù)千年的模式：不再從標(biāo)準(zhǔn)公理集出發(fā)證明定理，而是用一個定理替換其中一條公理，再去證明那條原本的公理。

這種方法被稱為 “反向數(shù)學(xué)” reverse mathematics，他們借此證明了復(fù)雜性理論中許多看似截然不同的定理實際上在邏輯上是等價的。

“他們能完成這么多工作，我感到很驚訝，”IBM 的復(fù)雜性理論學(xué)家馬爾科?卡爾莫西諾（Marco Carmosino）表示，“人們看到這項成果后，可能會說‘這就是讓我投身元數(shù)學(xué)的原因’?！?/p>

鴿籠原理的證明

這篇反向數(shù)學(xué)論文的故事始于 2022 年夏天，當(dāng)時即將在加州大學(xué)伯克利分校獲得博士學(xué)位的復(fù)雜性理論學(xué)家陳立杰（Lijie Chen）正處于學(xué)業(yè)收尾階段。他手頭有了不少空閑時間，決定花幾個月時間鉆研元數(shù)學(xué)。

陳立杰想到了一種方法，可顛倒兩個數(shù)學(xué)定理之間的邏輯關(guān)系。

圖源：Hongxun Wu

“因為快要畢業(yè)了，沒什么太多研究要做，” 陳立杰說，“我想我應(yīng)該學(xué)點新東西?！痹陂喿x過程中，陳立杰開始關(guān)注復(fù)雜性理論的一個分支 ——通信復(fù)雜性communication complexity。該領(lǐng)域研究的是兩個或多個人為完成特定任務(wù)必須交換的信息量。

通信復(fù)雜性中一個最簡單的問題是 “相等性問題”，類似一個協(xié)作游戲：兩名參與者各自持有一串由 0 和 1（即比特）組成的字符串，目標(biāo)是用最少的通信量判斷彼此的字符串是否相同。最簡單的策略是其中一人發(fā)送完整字符串供另一人核對，但有沒有更優(yōu)的方法呢？

復(fù)雜性理論學(xué)家數(shù)十年前就已證明答案是否定的：要解決相等性問題，參與者至少需要發(fā)送與完整字符串長度相等的比特數(shù)。理論學(xué)家稱這個字符串長度是所需通信量的 “下界”。

陳立杰關(guān)注的并非相等性問題的下界本身，而是研究人員證明這一下界的方法。所有已知證明都依賴于一個簡單的定理 ——鴿籠原理，該原理指出：如果將若干只鴿子放入數(shù)量更少的鴿籠中，那么至少有一個鴿籠中會有多只鴿子。這聽起來或許顯而易見，但在復(fù)雜性理論及其他領(lǐng)域，它卻是一種出人意料的強(qiáng)大工具。陳立杰突然意識到一個有趣的可能性：相等性問題與鴿籠原理之間的聯(lián)系或許是雙向的。用鴿籠原理證明相等性問題的下界很容易，但反過來，能否用這個下界證明鴿籠原理呢？

奇妙的等價關(guān)系

陳立杰與當(dāng)時清華大學(xué)的本科生李嘉圖（Jiatu Li）討論了自己的想法 —— 兩人此前剛合作完成另一篇論文。要使這種聯(lián)系嚴(yán)謹(jǐn)化，他們需要選擇一套公理作為研究基礎(chǔ)。元數(shù)學(xué)研究人員更傾向于使用比常規(guī)公理更具限制性的公理，這些較弱的公理能更精準(zhǔn)地界定不同定理之間的關(guān)系。陳立杰和李嘉圖決定采用一套名為 PV?的常用公理 https://dl.acm.org/doi/10.1145/800116.803756 。

PV?本身足以證明計算復(fù)雜性領(lǐng)域的一些重要定理，若再加入鴿籠原理的一個特定版本作為額外公理，還能證明相等性問題的下界。2022年12月，李嘉圖和陳立杰正式證明，正如陳立杰猜想的那樣，將這兩個定理互換后，證明依然成立。

伊戈爾?奧利維拉（Igor Oliveira）助力證明了許多看似不同的定理實際上是等價的。

圖源：Richard Cunningham

若能從鴿巢原理推導(dǎo)出相等性問題的下界，反之亦然 —— 這一事實表明，在 PV?的邏輯框架內(nèi)，這兩個定理是完全等價的。沃里克大學(xué)的復(fù)雜性理論學(xué)家伊戈爾?奧利維拉（Igor Oliveira）與兩人討論了這一結(jié)果，三人意識到，這種反向數(shù)學(xué)方法或許也適用于復(fù)雜性理論其他遙遠(yuǎn)領(lǐng)域的定理。在接下來的幾個月里，他們系統(tǒng)地證明了許多其他定理之間的等價關(guān)系。

“一開始，我們只發(fā)現(xiàn)了兩個等價的定理，” 陳立杰說，“但現(xiàn)在我們已經(jīng)構(gòu)建出一個龐大的等價網(wǎng)絡(luò)?！?/p>

看似不同，實則等價

插圖來源：Mark Belan / Quanta Magazine

以下三個表面上截然不同的定理在邏輯上是等價的：

鴿籠原理

若將若干只鴿子放入數(shù)量更少的鴿籠中，則至少有一個鴿籠中會有多只鴿子。

相等性下界

兩名持有不同信息的參與者，要判斷各自信息是否完全相同，必須共享一定最低量的信息。

回文下界

單帶圖靈機(jī)要判斷一串比特是否為回文（即正讀和反讀完全一致），需要一定的最低時間。

該團(tuán)隊發(fā)現(xiàn)的最驚人關(guān)聯(lián)，是將同一版本的鴿籠原理與復(fù)雜性理論入門課程中學(xué)生遇到的首批定理之一聯(lián)系了起來。正如卡爾莫西諾所描述的，這個 “經(jīng)典核心定理” 為一類名為 “單帶圖靈機(jī)” https://www.quantamagazine.org/alan-turings-most-important-machine-was-never-built-20230503/ 的理論計算機(jī)設(shè)定了下界 —— 判斷一串 0 和 1 組成的字符串是否為回文（palindrome）所需的最低時間。李嘉圖、陳立杰和奧利維拉運用反向數(shù)學(xué)證明，在 PV?的邏輯框架內(nèi)，這個回文下界定理與鴿籠原理是等價的。

“如果有人提前告訴我這個結(jié)論，我肯定不會相信，” 陳立杰說，“這聽起來太荒謬了?！?/p>

回文下界與鴿籠原理的等價性之所以令人驚訝，是因為兩者表面上差異巨大。鴿籠原理本質(zhì)上與計算無關(guān)，只是一個關(guān)于計數(shù)的簡單表述；而回文下界則是關(guān)于特定計算模型的命題。這一新結(jié)果表明，這類看似狹窄的定理實際上比表面看起來更具普遍性?！斑@意味著我們想要理解的這些復(fù)雜性下界，其基礎(chǔ)性遠(yuǎn)比我們想象的更強(qiáng)，” 奧利維拉說。

未知領(lǐng)域

這個新的等價網(wǎng)絡(luò)也幫助揭示了 PV?公理的局限性。研究人員早已認(rèn)為，僅靠 PV?的公理無法證明鴿籠原理，因此李嘉圖、陳立杰和奧利維拉的結(jié)果意味著，與鴿籠原理等價的其他定理在 PV?中也可能無法證明。

“我覺得這一成果非常美妙，” 牛津大學(xué)的復(fù)雜性理論學(xué)家揚?皮希（Ján Pich）說。他在 2014 年證明了一項關(guān)于 PV?公理能力的重要成果 https://arxiv.org/abs/1412.3246 ，但他也提醒道，反向數(shù)學(xué)方法最有用的地方或許是揭示研究人員已證明定理之間的新關(guān)聯(lián)，“就目前而言，它對我們尚未知曉如何證明的命題的復(fù)雜性，并沒有提供太多信息?！?/p>

對于元數(shù)學(xué)研究人員來說，理解這片未知領(lǐng)域仍是一個遙遠(yuǎn)的目標(biāo)，但這并未削弱李嘉圖對該領(lǐng)域的熱情。他于2023年進(jìn)入麻省理工學(xué)院攻讀研究生，并最近撰寫了一份長達(dá) 140 頁的復(fù)雜性理論學(xué)家元數(shù)學(xué)指南《面向計算機(jī)科學(xué)家的可行數(shù)學(xué)與有界算術(shù)導(dǎo)論》

An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists

“人們已經(jīng)厭倦了陷入困境，” 卡爾莫西諾說，“現(xiàn)在是時候退一步，打好基礎(chǔ)了?！?/p>

參考資料

https://www.quantamagazine.org/reverse-mathematics-illuminates-why-hard-problems-are-hard-20251201/

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

https://eccc.weizmann.ac.il/report/2024/060/

https://dl.acm.org/doi/10.1145/800116.803756

https://www.quantamagazine.org/alan-turings-most-important-machine-was-never-built-20230503/

https://arxiv.org/abs/1412.3246

https://eccc.weizmann.ac.il/report/2025/086/

小樂數(shù)學(xué)科普近期文章

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

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

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

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

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

置頂加星★

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