“反向數學”揭示難題為何難解——量子雜志

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

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

在反向數學領域中，研究人員會用他們想要證明的定理，去替換數學系統的基礎 —— 公理。

圖源：Son of Alan for Quanta Magazine

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

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

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

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

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

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

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

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

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

鴿籠原理的證明

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

陳立杰想到了一種方法，可顛倒兩個數學定理之間的邏輯關系。

圖源：Hongxun Wu

“因為快要畢業了，沒什么太多研究要做，” 陳立杰說，“我想我應該學點新東西。”在閱讀過程中，陳立杰開始關注復雜性理論的一個分支 ——通信復雜性communication complexity。該領域研究的是兩個或多個人為完成特定任務必須交換的信息量。

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

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

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

奇妙的等價關系

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

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

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

圖源：Richard Cunningham

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

“一開始，我們只發現了兩個等價的定理，” 陳立杰說，“但現在我們已經構建出一個龐大的等價網絡。”

看似不同，實則等價

插圖來源：Mark Belan / Quanta Magazine

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

鴿籠原理

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

相等性下界

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

回文下界

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

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

“如果有人提前告訴我這個結論，我肯定不會相信，” 陳立杰說，“這聽起來太荒謬了。”

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

未知領域

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

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

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

An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists

“人們已經厭倦了陷入困境，” 卡爾莫西諾說，“現在是時候退一步，打好基礎了。”

參考資料

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/

小樂數學科普近期文章

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

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

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

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

置頂加星★

數學科普不迷路！