清华姚班学霸联手，提出“逆向数学”：为破解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。