清華姚班學霸聯手，提出“逆向數學”：為破解50年計算難題點亮新路

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

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

這項工作并未正面給出難題的答案，但它以一種顛覆性的視角，揭示了“我們為何被卡住”，并為整個領域指明了新的探索方向。

一、五十年的嘆息之墻：我們為何卡住了？

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

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

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

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

這個問題，跳出了具體的數學問題，進入了研究“證明”本身的“元數學”領域。

二、一個顛覆性想法：把數學“倒過來”！

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

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

在閱讀中，他關注到通信復雜性里一個經典問題——“相等性問題”：兩個人各自有一串由0和1組成的密碼，他們如何用最少的對話，判斷兩人的密碼是否完全相同？幾十年前，科學家就證明，最有效的方法也必須發送與密碼長度相當的信息量。而這個證明，依賴于一個家喻戶曉的原理——鴿巢原理（把n+1只鴿子放進n個籠子，至少有一個籠子有兩只鴿子）。

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

三、驚人的“等價網絡”：從鴿子籠到計算機回文

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

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

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

“如果你直接告訴我這個結論，我肯定不信。聽起來太扯了。”陳立杰本人也曾對這個發現感到難以置信。一個看似與計算無關的簡單數數原理，竟和一個關于特定計算模型性能的深層定理，在邏輯底層是同一回事。

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

四、新發現的意義：我們為何卡住，以及未來何去何從

這張精妙的“等價關系網”不僅漂亮，更重要的是，它為“我們為何卡住了半個世紀”提供了一個深刻的答案。

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

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

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

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

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

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

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

結語

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

當所有人都在奮力向前沖鋒，試圖推倒那堵“嘆息之墻”時，這群清華學子選擇停下來，后退一步，開始審視大家腳下共同站立的地基是否堅實。這或許正是基礎科學最迷人的地方——它不僅關乎找到答案，更關乎我們如何提出更好的問題。

正如一位研究者所感慨：“大家已經厭倦了被卡在原地不動，是時候退一步，好好把地基搞搞清楚了。”而陳立杰、李嘉圖及伊戈爾·奧利維拉，正是這場至關重要的“地基勘察”中，最耀眼的先行者。

參考文獻

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

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

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

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

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

文章來源：水木TsinghuaCent。