當(dāng)全球的科學(xué)家都在奮力向前沖，試圖用更復(fù)雜的公式正面攻克“旅行商問題”等計算難題時，幾位來自中國清華大學(xué)的青年學(xué)者選擇停下腳步，轉(zhuǎn)身開始審視他們腳下賴以站立的理論“地基”。

2024年4月，一篇名為《復(fù)雜性下界的逆向數(shù)學(xué)》的學(xué)術(shù)論文低調(diào)上線，卻在全球理論計算機科學(xué)界引發(fā)了持續(xù)震動。這篇由三位學(xué)者——清華“姚班”校友陳立杰、在校本科生李嘉圖，以及華威大學(xué)的學(xué)者伊戈爾·奧利維拉——共同完成的論文，采用了一種被稱為“逆向數(shù)學(xué)”的全新思路，為困擾學(xué)界長達半個世紀(jì)的核心難題提供了一份深刻的“診斷報告”。

這項工作并未正面給出難題的答案，但它以一種顛覆性的視角，揭示了“我們?yōu)楹伪豢ㄗ　?，并為整個領(lǐng)域指明了新的探索方向。

一、五十年的嘆息之墻：我們?yōu)楹慰ㄗ×耍?/strong>

理解這項突破，要從計算機科學(xué)界一道著名的“嘆息之墻”說起。

想象一下“旅行商問題”：一位推銷員需要拜訪多個城市，每個城市只去一次，最后回到起點，如何找到最短路線？當(dāng)城市數(shù)量增加，可能的路線組合便會爆炸式增長，即使是全球最快的超級計算機也可能需要宇宙年齡那么長的時間來求解。

科學(xué)家們的普遍直覺是：這類問題本質(zhì)上就“很難”，不存在一個聰明的通用捷徑能快速解決。然而，真正的核心難題在于：如何用嚴(yán)密的數(shù)學(xué)語言，證明這種“難”？這就是計算復(fù)雜性理論中，證明問題“下界”的挑戰(zhàn)。

半個世紀(jì)以來，無數(shù)頂尖頭腦投入其中，卻始終無法取得決定性的突破。這道“嘆息之墻”迫使人們反思一個更根本的元問題：我們證明不了，是不是因為我們所使用的證明工具本身——即那些基礎(chǔ)的數(shù)學(xué)公理體系——就存在局限性？

這個問題，跳出了具體的數(shù)學(xué)問題，進入了研究“證明”本身的“元數(shù)學(xué)”領(lǐng)域。

二、一個顛覆性想法：把數(shù)學(xué)“倒過來”！

傳統(tǒng)的數(shù)學(xué)研究，遵循著“公理→定理”的路徑，如同從地基開始建造大廈。而陳立杰團隊的想法堪稱“離經(jīng)叛道”。他們沒有選擇從基礎(chǔ)公理出發(fā)，去艱難地“建造”那個證明，而是采用了“逆向數(shù)學(xué)”的思路：先假設(shè)某個定理（比如“某個計算問題很難”）是對的，然后反過來追問——究竟需要多強的基礎(chǔ)公理，才能推導(dǎo)出它？

這個故事的起點頗具個人色彩。2022年夏天，即將從麻省理工學(xué)院（MIT）博士畢業(yè)的陳立杰有了一段相對空閑的時間。在談及最初探索元數(shù)學(xué)(Metamathematics）的動機時，他曾簡單地說：“我要畢業(yè)了，也沒多少研究任務(wù)了，就尋思著該學(xué)點新東西。”

在閱讀中，他關(guān)注到通信復(fù)雜性里一個經(jīng)典問題——“相等性問題”：兩個人各自有一串由0和1組成的密碼，他們?nèi)绾斡米钌俚膶υ挘袛鄡扇说拿艽a是否完全相同？幾十年前，科學(xué)家就證明，最有效的方法也必須發(fā)送與密碼長度相當(dāng)?shù)男畔⒘?。而這個證明，依賴于一個家喻戶曉的原理——鴿巢原理（把n+1只鴿子放進n個籠子，至少有一個籠子有兩只鴿子）。

陳立杰敏銳地捕捉到了一個可能雙向的聯(lián)系：既然“鴿巢原理”能用來證明“相等性問題”的難度下界，那么，反過來呢？“相等性問題”的難度下界，能否反過來證明“鴿巢原理”？

三、驚人的“等價網(wǎng)絡(luò)”：從鴿子籠到計算機回文

為了驗證這個大膽的猜想，陳立杰和當(dāng)時還是本科生的李嘉圖組隊，選擇了一套計算理論中基礎(chǔ)的公理體系“PV?”作為“試驗場”。經(jīng)過數(shù)月的努力，他們在2022年12月取得了成功：在PV?的框架內(nèi)，他們嚴(yán)格證明了“相等性問題的通信復(fù)雜度下界”與某個特定版本的“鴿巢原理”在邏輯上是完全等價的。

這意味著，在這套邏輯體系里，你能證明其中一個，就必然能證明另一個。這還只是個開始。在與資深學(xué)者奧利維拉合作后，他們迅速將這張“等價之網(wǎng)”鋪開。

其中最令人震驚的發(fā)現(xiàn)是，同一個“鴿巢原理”，竟然與計算機科學(xué)入門課上的另一個經(jīng)典定理等價：單帶圖靈機判斷一個字符串是否為“回文”（如“上海自來水來自海上”）所需時間復(fù)雜度的下界。

“如果你直接告訴我這個結(jié)論，我肯定不信。聽起來太扯了?！标惲⒔鼙救艘苍鴮@個發(fā)現(xiàn)感到難以置信。一個看似與計算無關(guān)的簡單數(shù)數(shù)原理，竟和一個關(guān)于特定計算模型性能的深層定理，在邏輯底層是同一回事。

這一系列等價性證明，揭示了那些看似狹窄、技術(shù)性的“難度下界”定理，其本質(zhì)遠比我們想象的更基礎(chǔ)、更普適。它們不再是孤立的技術(shù)結(jié)論，而是與數(shù)學(xué)中最核心的組合原理緊密相連的“基本公理”。

四、新發(fā)現(xiàn)的意義：我們?yōu)楹慰ㄗ?，以及未來何去何?/strong>

這張精妙的“等價關(guān)系網(wǎng)”不僅漂亮，更重要的是，它為“我們?yōu)楹慰ㄗ×税雮€世紀(jì)”提供了一個深刻的答案。

長期以來，邏輯學(xué)家們普遍相信，僅靠PV?這個基礎(chǔ)理論，是無法證明“鴿巢原理”的。那么，根據(jù)陳立杰團隊的等價性證明，一個直接的推論就是：所有與“鴿巢原理”等價的復(fù)雜性下界（比如著名的“回文問題下界”），同樣無法在PV?中被證明！

他們的研究甚至更進一步。論文指出，在一個比PV?更強的理論中，基于一個廣為接受的密碼學(xué)假設(shè)，經(jīng)典的“回文下界”仍然是不可證明的。這顛覆了許多研究者認為大多數(shù)下界都可以在更強理論中解決的直覺。

這項工作還揭示了一種“放大現(xiàn)象”：在某些情況下，證明一個看似較弱的、非緊確的下界，和證明一個更強（甚至是緊確）的下界，其難度是完全一樣的。這意味著，在證明下界的道路上，可能不存在“循序漸進”的輕松路徑，試圖先證明一個弱版本作為跳板，在邏輯上并不總是有效。

牛津大學(xué)的復(fù)雜性理論家雅恩·皮奇評價道：“我覺得這太美了。”但他同時指出，逆向數(shù)學(xué)目前更擅長揭示已知定理間的聯(lián)系，對于尚未解決的終極難題（如P vs NP），它提供的信息可能還很有限。

但這正是這項工作的真正價值所在。它標(biāo)志著一種研究范式的轉(zhuǎn)變。在正面強攻數(shù)十年后，它吸引整個領(lǐng)域“退一步”，去重新審視和加固理論大廈的根基。正如李嘉圖為同行撰寫的長達140頁的元數(shù)學(xué)入門指南所展示的，打好地基，才能理解未知。

五、群星閃耀：幕后的天才

這項突破由三位杰出的學(xué)者共同完成。陳立杰是清華大學(xué)姚班知名校友，在理論計算機科學(xué)領(lǐng)域已是頂尖的青年學(xué)者。早在2013年，他便以世界第一的成績獲得國際信息學(xué)奧林匹克（IOI）金牌。本科期間，他成為首位在理論計算機頂會FOCS上發(fā)表論文的中國本科生。2025年秋季起，他正式成為加州大學(xué)伯克利分校EECS的助理教授。他的合作者李嘉圖，在參與這項研究時還是清華姚班的本科生，展現(xiàn)了驚人的理論天賦和深度。資深合作者伊戈爾·奧利維拉則是華威大學(xué)的教授，他的經(jīng)驗幫助團隊將最初的發(fā)現(xiàn)拓展到了更廣闊的領(lǐng)域。

結(jié)語

陳立杰團隊的工作并未直接解決P vs NP這樣的終極難題，但它從一個全新的維度，揭示了這些難題“難”在何處。它告訴我們，有時最大的突破并非來自更猛烈的火力，而是來自視角的徹底轉(zhuǎn)變。

當(dāng)所有人都在奮力向前沖鋒，試圖推倒那堵“嘆息之墻”時，這群清華學(xué)子選擇停下來，后退一步，開始審視大家腳下共同站立的地基是否堅實。這或許正是基礎(chǔ)科學(xué)最迷人的地方——它不僅關(guān)乎找到答案，更關(guān)乎我們?nèi)绾翁岢龈玫膯栴}。

正如一位研究者所感慨：“大家已經(jīng)厭倦了被卡在原地不動，是時候退一步，好好把地基搞搞清楚了?！倍惲⒔堋⒗罴螆D及伊戈爾·奧利維拉，正是這場至關(guān)重要的“地基勘察”中，最耀眼的先行者。

參考文獻

1. 清華姚班大神陳立杰獲UC伯克利教職，2025年秋季入職。量子位。

2. 清華姚班大神陳立杰，聯(lián)手00后逆向破局！顛覆50年計算機難題。新智元。

3. 我立志為人類智慧添磚加瓦——訪清華大學(xué)2016年本科生特等獎學(xué)金獲得者陳立杰。清華大學(xué)新聞網(wǎng)。

4. 清華姚班出身，95后博士生陳立杰獲理論計算機頂會最佳學(xué)生論文。界面新聞。

5. 清華天才把數(shù)學(xué)“倒過來”，竟撼動了計算機科學(xué)半個世紀(jì)的難題。極思TopMinds。

文章來源：水木TsinghuaCent。