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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

結(jié)語

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

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

正如一位研究者所感慨：“大家已經(jīng)厭倦了被卡在原地不動，是時(shí)候退一步，好好把地基搞搞清楚了?！倍惲⒔?、李嘉圖及伊戈?duì)枴W利維拉，正是這場至關(guān)重要的“地基勘察”中，最耀眼的先行者。

參考文獻(xiàn)

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

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

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

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

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

文章來源：水木TsinghuaCent。