新智元報道

編輯：桃子 好困

50年未解計算復雜性「天坑」，竟被姚班大神搞定了！他選了一條「逆向數學」的新路，正把理論計算機科學倒過來重寫。

清華姚班大神，再度引爆理論計算機科學圈！

50年來，頂尖科學家都在死磕「旅行商問題」等這類計算機復雜性難題，卻遲遲沒有進展。

為什么一直證明不出來？

實際上，答案藏在了「元數學」的領域。

恰在去年，一篇名為《Reverse Mathematics Below the Turing Jump》論文低調上線。

作者僅有三個人，清華姚班陳立杰、本科生李嘉圖，以及著名計算機領域學者Igor Carboni Oliveira。

論文地址：https://eccc.weizmann.ac.il/report/2024/060/

他們不再死磕從公理推導定理的傳統路徑，而是另辟蹊徑，采用了「元數學」中「逆向數學」的方法。

結果驚喜地發現，許多看似風馬牛不相及的理論，竟在底層邏輯中是完全等價的。

比如，「鴿巢原理」與圖靈機的「回文下界」。

這篇論文一出，徹底顛覆了人們的「世界觀」。

過去半個世紀，計算機科學家們苦苦追求「更強公理證明更難定理」的思路，原來從一開始就走偏了。

把數學「倒過來」

顛覆千年思維范式

一提到那些「硬骨頭」難題，計算機科學家們似乎就卡殼了。

就以著名的「旅行商問題」為例，表面上看，這只是一個組合優化問題：

在地圖上找一條經過每個城市恰好一次，最后還能回到起點的最短路線。

可是一旦城市數量稍多，科學家也就懷疑：根本沒有很好的辦法。但問題是，沒人知道怎么證明這一點。

過去50年來，計算復雜性理論領域的大佬，都嘗試把這種「直覺」，轉化成板上釘釘的數學定理。

實際上，他們一次次鎩羽而歸，根本找不到任何突破口。

這也讓他們越來越多地開始琢磨一個相關但更讓人摸不著頭腦的問題：為啥證明老是不成功呢？

「元數學」（metamathematics），卻把證明本身當成了研究對象。

當研究人員用「元數學」研究復雜性理論時，他們試圖搞清楚——

用不同的公理集，到底能證明/不能證明關于計算難度的哪些結論。

為啥自己在證明「問題很難」這條路上，總是差了一口氣。

2024年4月這篇論文，做了一件前人都不敢想的事：三人團隊徹底顛倒了數學幾千年來的思維范式。

傳統的套路是，給到一套公理，推出一串定理。

而現在，他們反過來——用一個定理替換掉其中一條公理，然后去證明那條被替換掉的公理。

正如論文題目所示，這一過程稱之為「逆向數學」（Reverse Mathematics）。

它證明了，一大堆看起來完全不相關的「復雜性定理」，其實邏輯完全等價。

IBM復雜性理論家Marco Carmosino看到論文后的第一反應，「我震驚了，他們居然能做出這么多東西」。

誰看了肯定都會說，就是它把我拽進了「元數學」這個坑的！

鴿子證明，離經叛道

故事還得從2022年夏天說起。

當時，陳立杰正準備MIT博士畢業，發現手頭突然多出了一大把空閑時間，便決定花幾個月鉆研一下元數學。

他表示，「因為我要畢業了嘛，也沒多少研究任務了，就尋思著該學點新東西」。

讀著讀著，陳立杰開始琢磨起復雜性理論的一個分支——通信復雜性（communication complexity）。

主要研究兩個或多個人為了完成某項任務，必須交換多少信息。

在通信復雜性里，有個最簡單的問題叫「相等性問題」（equality problem），就像個合作游戲：

兩個玩家各自拿著一串0和1組成的字符串，目標是用最少的交流，弄清楚對方手里的字符串是不是一模一樣的。

最笨的辦法就是，一個玩家把自己的字符串整個兒發給對方檢查。

除此之外，復雜性理論家幾十年前就證明了：沒招，不行。

要解決「相等性問題」，至少得發送跟字符串長度一樣多的比特數。理論家把這個字符串的長度稱為所需通信量的「下界」（lower bound）。

陳立杰關注的不是這個「下界」本身，而是研究人員當初是怎么證明它的。

而所有已知的證明都離不開一個簡單的定理——鴿巢原理（pigeonhole principle，也叫「抽屜原理」）。

這原理說的是：如果你把一堆鴿子塞進比鴿子數量少的洞里，那至少有一個洞里得擠著不止一只鳥。

這聽起來好像是廢話，但在復雜性理論以及更多領域里，這可是個威力巨大的工具。

于是，陳立杰敏銳地捕捉到一個重要的線索——

「相等性問題」和「鴿巢原理」之間的聯系，沒準是雙向的。

用鴿巢原理來證明相等性問題的下界很容易。那能不能反過來，用下界來證明鴿巢原理呢？

離奇的相等

于是，陳立杰拉上了剛合作完一篇論文清華本科生李嘉圖（Jiatu Li），開始了新的探索。

為了讓這種聯系在數學上站得住腳，他們得選定一套公理作為「地基」。

他們選了一套很流行的公理集，叫PV?，開始「逆向」。

因為PV?本身足夠強，能獨立證明計算復雜性里的一些重要定理，若在PV?基礎上，再加一條特定版「鴿巢原理」作為額外公理，就能證明「相等性問題」的下界。

2022年12月，他們成功了！

結果恰恰驗證了陳立杰最初的猜想：把定理的位置互換一下，證明也依然成立。

在PV?邏輯框架中，兩個定理是完全等價的。

當他們跟華威大學的復雜性理論家Igor Oliveira聊起結果時，突然意識到——

「逆向數學」大法，可能也適用于復雜性理論中其他八竿子打不著的領域。

在接下來幾個月里，他們系統地證明了許多其他定理也是等價的。

陳立杰說，「剛開始，我們要證的等價東西只有倆，但現在我們手里已經織出了一張大網」。

這個團隊發現的最驚人的聯系，是把同一個版本的「鴿巢原理」，跟學生們在復雜性理論入門課上學到的最早那批定理之一聯系了起來。

這一經典定理，設定了一種理論計算機，即單帶圖靈機（single-tape Turing machine），在判斷一串0和1是不是回文（正著讀反著讀都一樣）時，所需時間的下界。

「逆向數學」證明了：在PV?框架內，這個「回文下界」定理跟鴿巢原理竟然是等價的。

就連陳立杰難以置信地表示，「如果你直接告訴我這個結論，我肯定不信。聽起來太扯了」。

這一結論之所以讓人大跌眼鏡，是因為兩個定理表面上差得太遠了。

「鴿巢原理」本質上跟計算沒任何關系，是個關于數數的簡單道理。

而回文下界呢，是關于特定計算模型的一條陳述。

這個新結果意味著，這些看似路子很窄的定理，其實比它們看起來要通用得多，基礎得多。

Oliveira表示，「這說明我們想要理解的這些復雜性下界，其實更加觸及根本」。

未知領域，還需打好地基

令人欣喜的是，這張新的「等價關系網」也幫科學家們看清了PV?的局限性。

大家早就相信，光靠PV?的公理是證明不了「鴿巢原理」的。

所以，論文的結果就意味著，網里的其他等價定理，在PV?里多半也是證明不了的。

牛津大學的復雜性理論家Ján Pich感嘆道，「我覺得這太美了」。

但他同時提醒道，「逆向數學」這種方法，可能最適合用來揭示那些已經被證明出來的定理之間的新聯系。

「對于那些我們還不知道怎么證明的陳述，就目前來看，它能告訴我們的關于其復雜性的信息并不多」。

要搞懂這片未知領域，對「元數學」研究人員來說還是個遙遠的目標。

但這絲毫沒有澆滅李嘉圖對這個學科的熱情。

2023年進入MIT攻讀研究生，他最近還專門為復雜性理論家寫了一份長達140頁的元數學指南。

論文地址：https://eccc.weizmann.ac.il/report/2025/086/

這也是一個大趨勢的縮影：即便坐了幾十年的冷板凳后，「元數學」正日益吸引著更廣泛的研究人員群體的目光，他們正給這個領域帶來全新的視角。

Carmosino表示，「大家已經厭倦了被卡在原地不動，是時候退一步，好好把地基搞搞清楚了」。

作者介紹

陳立杰

陳立杰是加州大學伯克利分校電氣工程與計算機科學系（EECS）的助理教授，也是伯克利理論組的一員。

早在高中時期，陳立杰就已在信息學競賽圈封神，展現出了超越同齡人的編程天賦與數學洞察力。

2012年NOI大賽中，陳立杰以金牌成績脫穎而出，提前鎖定了清華大學的保送資格。

緊接著，在第25屆IOI上，他又以569分（滿分600分）的驚人成績奪得全球第一。

一直以來，他還在Codeforces、TopCoder等國際編程平臺上長期霸榜，因其解題速度極快、思路極其實用，被國內外選手膜拜。

保送到清華大學后，陳立杰在交叉信息研究院「姚班」獲得學士學位，師從李建教授。

2016年，他曾獲得了清華本科生特等獎學金，答辯視頻一度火爆全網。

隨后，他在MIT獲得了博士學位，師從Ryan Williams。

當時，他的主攻方向是「計算復雜性理論」和「細粒度復雜性」。

2019年，他包攬了理論計算機科學領域兩大頂級會議（STOC和FOCS）的最佳學生論文獎。

2022年博士畢業后，他獲得了極具聲望的加州大學伯克利分校米勒獎學金（Miller Fellowship），成為該校的博士后研究員，合作導師是Avishay Tal和Umesh V. Vazirani。

他對理論計算機科學有著廣泛的興趣，特別是復雜度理論中的基礎性問題。同時，也致力于將理論計算機科學的思想應用到其他科學領域，例如量子物理和AI安全。

如何在P vs. NP問題上取得進展？

隨機性對于高效計算而言是不可或缺的嗎？（即BPP是否等于P？）

量子復雜度理論如何幫助我們理解量子物理？

如何應用理論計算機科學的思想，為AI系統建立安全理論保障？

科研，只是陳立杰眾多興趣之一。在清華一次采訪中，他曾提到如果未來不做研究，就做音樂游戲玩家。

成為一名真正的理論計算機科學家，這個想法從中學時期在他的內心就已生根發芽。

如今，回看他的研究和職業生涯，正是朝著這個方向一直在發光發亮。

李嘉圖

李嘉圖是MIT理論組的二年級博士生，師從Ryan Williams。

此前，他在清華大學交叉信息院「姚班」獲得學士學位。期間，他曾與華威大學的Igor C. Oliveira以及清華大學的陳一鐳教授有過合作。

他的研究集中在證明計算的固有難度（即電路復雜度）、證明系統（即證明復雜度），以及探究為什么這個研究方向如此困難（即元復雜度）。

最近，他對以下方向也很感興趣：有界算術（Bounded Arithmetic）的強度，值域規避問題（Range Avoidance Problem）的復雜度，證明無條件復雜度下界，以及使用Coq和Lean編寫形式化數學證明。

在他看來，復雜度理論研究者的使命，就是「解救」那些試圖攻克固有難題的勇士們。有時候，這些難題的故事也能治好密碼學家的失眠（譬如這篇：Cryptographers Seldom Sleep Well）。

Igor Carboni Oliveira

Igor C. Oliveira是華威大學理論與基礎學部（FoCS）以及離散數學及其應用中心（DIMAP）的成員。

此前，他在哥倫比亞大學計算理論組獲得了博士學位，并曾是牛津大學算法與復雜度理論組的博士后研究員，加州大學伯克利分校Simons研究所的研究員，以及布拉格查理大學數學學院的博士后。

他研究集中在計算復雜度理論，以及該領域與算法、組合數學和數理邏輯之間的聯系。研究興趣是高效計算的可能性與局限性，以及我們能對此證明些什么。

參考資料：

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

秒追ASI

?點贊、轉發、在看一鍵三連?

點亮星標，鎖定新智元極速推送！