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

清華姚班大神，再度引爆理論計算機(jī)科學(xué)圈！

50年來，頂尖科學(xué)家都在死磕「旅行商問題」等這類計算機(jī)復(fù)雜性難題，卻遲遲沒有進(jìn)展。

為什么一直證明不出來？

實(shí)際上，答案藏在了「元數(shù)學(xué)」的領(lǐng)域。

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

作者僅有三個人，清華姚班陳立杰、本科生李嘉圖，以及著名計算機(jī)領(lǐng)域?qū)W者Igor Carboni Oliveira。

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

他們不再死磕從公理推導(dǎo)定理的傳統(tǒng)路徑，而是另辟蹊徑，采用了「元數(shù)學(xué)」中「逆向數(shù)學(xué)」的方法。

結(jié)果驚喜地發(fā)現(xiàn)，許多看似風(fēng)馬牛不相及的理論，竟在底層邏輯中是完全等價的。

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

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

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

把數(shù)學(xué)「倒過來」

顛覆千年思維范式

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

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

在地圖上找一條經(jīng)過每個城市恰好一次，最后還能回到起點(diǎn)的最短路線。

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

過去50年來，計算復(fù)雜性理論領(lǐng)域的大佬，都嘗試把這種「直覺」，轉(zhuǎn)化成板上釘釘?shù)臄?shù)學(xué)定理。

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

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

「元數(shù)學(xué)」（Metamathematics），卻把證明本身當(dāng)成了研究對象。

當(dāng)研究人員用「元數(shù)學(xué)」研究復(fù)雜性理論時，他們試圖搞清楚——

用不同的公理集，到底能證明/不能證明關(guān)于計算難度的哪些結(jié)論。

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

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

傳統(tǒng)的套路是，給到一套公理，推出一串定理。

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

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

它證明了，一大堆看起來完全不相關(guān)的「復(fù)雜性定理」，其實(shí)邏輯完全等價。

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

誰看了肯定都會說，就是它把我拽進(jìn)了「元數(shù)學(xué)」這個坑的！

鴿子證明，離經(jīng)叛道

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

當(dāng)時，陳立杰正準(zhǔn)備MIT博士畢業(yè)，發(fā)現(xiàn)手頭突然多出了一大把空閑時間，便決定花幾個月鉆研一下元數(shù)學(xué)。

他表示，「因?yàn)槲乙厴I(yè)了嘛，也沒多少研究任務(wù)了，就尋思著該學(xué)點(diǎn)新東西」。

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

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

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

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

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

除此之外，復(fù)雜性理論家?guī)资昵熬妥C明了：沒招，不行。

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

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

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

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

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

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

「相等性問題」和「鴿巢原理」之間的聯(lián)系，沒準(zhǔn)是雙向的。

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

離奇的相等

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

為了讓這種聯(lián)系在數(shù)學(xué)上站得住腳，他們得選定一套公理作為「地基」。

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

因?yàn)镻V?本身足夠強(qiáng)，能獨(dú)立證明計算復(fù)雜性里的一些重要定理，若在PV?基礎(chǔ)上，再加一條特定版「鴿巢原理」作為額外公理，就能證明「相等性問題」的下界。

2022年12月，他們成功了！

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

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

當(dāng)他們跟華威大學(xué)的復(fù)雜性理論家Igor Oliveira聊起結(jié)果時，突然意識到——

「逆向數(shù)學(xué)」大法，可能也適用于復(fù)雜性理論中其他八竿子打不著的領(lǐng)域。

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

陳立杰說，「剛開始，我們要證的等價東西只有倆，但現(xiàn)在我們手里已經(jīng)織出了一張大網(wǎng)」。

這個團(tuán)隊發(fā)現(xiàn)的最驚人的聯(lián)系，是把同一個版本的「鴿巢原理」，跟學(xué)生們在復(fù)雜性理論入門課上學(xué)到的最早那批定理之一聯(lián)系了起來。

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

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

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

這一結(jié)論之所以讓人大跌眼鏡，是因?yàn)閮蓚€定理表面上差得太遠(yuǎn)了。

「鴿巢原理」本質(zhì)上跟計算沒任何關(guān)系，是個關(guān)于數(shù)數(shù)的簡單道理。

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

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

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

未知領(lǐng)域，還需打好地基

令人欣喜的是，這張新的「等價關(guān)系網(wǎng)」也幫科學(xué)家們看清了PV?的局限性。

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

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

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

但他同時提醒道，「逆向數(shù)學(xué)」這種方法，可能最適合用來揭示那些已經(jīng)被證明出來的定理之間的新聯(lián)系。

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

要搞懂這片未知領(lǐng)域，對「元數(shù)學(xué)」研究人員來說還是個遙遠(yuǎn)的目標(biāo)。

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

2023年進(jìn)入MIT攻讀研究生，他最近還專門為復(fù)雜性理論家寫了一份長達(dá)140頁的元數(shù)學(xué)指南。

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

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

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

作者介紹

陳立杰

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

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

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

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

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

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

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

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

當(dāng)時，他的主攻方向是「計算復(fù)雜性理論」和「細(xì)粒度復(fù)雜性」。

2019年，他包攬了理論計算機(jī)科學(xué)領(lǐng)域兩大頂級會議（STOC和FOCS）的最佳學(xué)生論文獎。

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

他對理論計算機(jī)科學(xué)有著廣泛的興趣，特別是復(fù)雜度理論中的基礎(chǔ)性問題。同時，也致力于將理論計算機(jī)科學(xué)的思想應(yīng)用到其他科學(xué)領(lǐng)域，例如量子物理和AI安全。

• 如何在P vs. NP問題上取得進(jìn)展？

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

• 量子復(fù)雜度理論如何幫助我們理解量子物理？

• 如何應(yīng)用理論計算機(jī)科學(xué)的思想，為AI系統(tǒng)建立安全理論保障？

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

成為一名真正的理論計算機(jī)科學(xué)家，這個想法從中學(xué)時期在他的內(nèi)心就已生根發(fā)芽。

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

李嘉圖

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

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

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

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

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

Igor Carboni Oliveira

Igor C. Oliveira是華威大學(xué)理論與基礎(chǔ)學(xué)部（FoCS）以及離散數(shù)學(xué)及其應(yīng)用中心（DIMAP）的成員。

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

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

參考資料：

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

文章來源：新智元。