“反向数学”揭示难题为何难解——量子杂志|原理|反向数学|图灵机|定理|量子杂志|鸽笼

★置顶zzllrr小乐公众号（主页右上角）数学科普不迷路！

研究人员运用元数学方法证明，某些表面上看似不同的定理，实际上在逻辑上是等价的。

在反向数学领域中，研究人员会用他们想要证明的定理，去替换数学系统的基础 —— 公理。

图源：Son of Alan for Quanta Magazine

作者：Ben Brubaker（量子杂志特约记者）2025-12-1

译者：zzllrr小乐（数学科普公众号）2025-12-13

面对难题时，计算机科学家们似乎陷入了困境。例如，那个著名的TSP“旅行商问题”—— 寻找一条能恰好经过地图上所有城市一次的最短往返路线。在城市数量众多的地图上，所有已知的求解方法都异常缓慢，研究人员怀疑不存在更高效的解法，却无人能证明这一点。

五十多年来， https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/ 计算复杂性理论领域的研究人员一直试图将 “旅行商问题很难” 这类直觉性表述转化为确凿的数学定理，但收效甚微。如今，他们越来越多地在探寻一个相关且更模糊的问题的严谨答案：为何他们的证明屡屡受挫？

这项将数学证明过程本身作为数学分析对象的研究，隶属于一个著名的高深领域 ——元数学。元数学学者常常审视作为所有证明起点的基本假设（即公理），他们会更换初始公理，进而探索这些变化对可证明定理的影响。

当研究人员运用元数学研究复杂性理论时，他们试图勾勒出不同公理集在计算难度方面能证明什么、不能证明什么。他们希望通过这种方式，弄明白为何在证明问题难度的过程中始终未能取得突破。

去年发表的一篇论文中 https://eccc.weizmann.ac.il/report/2024/060/ ，三位研究人员针对这一挑战提出了一种新方法。他们颠覆了数学家们沿用数千年的模式：不再从标准公理集出发证明定理，而是用一个定理替换其中一条公理，再去证明那条原本的公理。

这种方法被称为 “反向数学” reverse mathematics，他们借此证明了复杂性理论中许多看似截然不同的定理实际上在逻辑上是等价的。

“他们能完成这么多工作，我感到很惊讶，”IBM 的复杂性理论学家马尔科・卡尔莫西诺（Marco Carmosino）表示，“人们看到这项成果后，可能会说‘这就是让我投身元数学的原因’。”

鸽笼原理的证明

这篇反向数学论文的故事始于 2022 年夏天，当时即将在加州大学伯克利分校获得博士学位的复杂性理论学家陈立杰（Lijie Chen）正处于学业收尾阶段。他手头有了不少空闲时间，决定花几个月时间钻研元数学。

陈立杰想到了一种方法，可颠倒两个数学定理之间的逻辑关系。

图源：Hongxun Wu

“因为快要毕业了，没什么太多研究要做，” 陈立杰说，“我想我应该学点新东西。”在阅读过程中，陈立杰开始关注复杂性理论的一个分支 ——通信复杂性communication complexity。该领域研究的是两个或多个人为完成特定任务必须交换的信息量。

通信复杂性中一个最简单的问题是 “相等性问题”，类似一个协作游戏：两名参与者各自持有一串由 0 和 1（即比特）组成的字符串，目标是用最少的通信量判断彼此的字符串是否相同。最简单的策略是其中一人发送完整字符串供另一人核对，但有没有更优的方法呢？

复杂性理论学家数十年前就已证明答案是否定的：要解决相等性问题，参与者至少需要发送与完整字符串长度相等的比特数。理论学家称这个字符串长度是所需通信量的 “下界”。

陈立杰关注的并非相等性问题的下界本身，而是研究人员证明这一下界的方法。所有已知证明都依赖于一个简单的定理 ——鸽笼原理，该原理指出：如果将若干只鸽子放入数量更少的鸽笼中，那么至少有一个鸽笼中会有多只鸽子。这听起来或许显而易见，但在复杂性理论及其他领域，它却是一种出人意料的强大工具。陈立杰突然意识到一个有趣的可能性：相等性问题与鸽笼原理之间的联系或许是双向的。用鸽笼原理证明相等性问题的下界很容易，但反过来，能否用这个下界证明鸽笼原理呢？

奇妙的等价关系

陈立杰与当时清华大学的本科生李嘉图（Jiatu Li）讨论了自己的想法 —— 两人此前刚合作完成另一篇论文。要使这种联系严谨化，他们需要选择一套公理作为研究基础。元数学研究人员更倾向于使用比常规公理更具限制性的公理，这些较弱的公理能更精准地界定不同定理之间的关系。陈立杰和李嘉图决定采用一套名为 PV₁的常用公理 https://dl.acm.org/doi/10.1145/800116.803756 。

PV₁本身足以证明计算复杂性领域的一些重要定理，若再加入鸽笼原理的一个特定版本作为额外公理，还能证明相等性问题的下界。2022年12月，李嘉图和陈立杰正式证明，正如陈立杰猜想的那样，将这两个定理互换后，证明依然成立。

伊戈尔・奥利维拉（Igor Oliveira）助力证明了许多看似不同的定理实际上是等价的。

图源：Richard Cunningham

若能从鸽巢原理推导出相等性问题的下界，反之亦然 —— 这一事实表明，在 PV₁的逻辑框架内，这两个定理是完全等价的。沃里克大学的复杂性理论学家伊戈尔・奥利维拉（Igor Oliveira）与两人讨论了这一结果，三人意识到，这种反向数学方法或许也适用于复杂性理论其他遥远领域的定理。在接下来的几个月里，他们系统地证明了许多其他定理之间的等价关系。

“一开始，我们只发现了两个等价的定理，” 陈立杰说，“但现在我们已经构建出一个庞大的等价网络。”

看似不同，实则等价

插图来源：Mark Belan / Quanta Magazine

以下三个表面上截然不同的定理在逻辑上是等价的：

鸽笼原理

若将若干只鸽子放入数量更少的鸽笼中，则至少有一个鸽笼中会有多只鸽子。

相等性下界

两名持有不同信息的参与者，要判断各自信息是否完全相同，必须共享一定最低量的信息。

回文下界

单带图灵机要判断一串比特是否为回文（即正读和反读完全一致），需要一定的最低时间。

该团队发现的最惊人关联，是将同一版本的鸽笼原理与复杂性理论入门课程中学生遇到的首批定理之一联系了起来。正如卡尔莫西诺所描述的，这个 “经典核心定理” 为一类名为 “单带图灵机” https://www.quantamagazine.org/alan-turings-most-important-machine-was-never-built-20230503/ 的理论计算机设定了下界 —— 判断一串 0 和 1 组成的字符串是否为回文（palindrome）所需的最低时间。李嘉图、陈立杰和奥利维拉运用反向数学证明，在 PV₁的逻辑框架内，这个回文下界定理与鸽笼原理是等价的。

“如果有人提前告诉我这个结论，我肯定不会相信，” 陈立杰说，“这听起来太荒谬了。”

回文下界与鸽笼原理的等价性之所以令人惊讶，是因为两者表面上差异巨大。鸽笼原理本质上与计算无关，只是一个关于计数的简单表述；而回文下界则是关于特定计算模型的命题。这一新结果表明，这类看似狭窄的定理实际上比表面看起来更具普遍性。“这意味着我们想要理解的这些复杂性下界，其基础性远比我们想象的更强，” 奥利维拉说。

未知领域

这个新的等价网络也帮助揭示了 PV₁公理的局限性。研究人员早已认为，仅靠 PV₁的公理无法证明鸽笼原理，因此李嘉图、陈立杰和奥利维拉的结果意味着，与鸽笼原理等价的其他定理在 PV₁中也可能无法证明。

“我觉得这一成果非常美妙，” 牛津大学的复杂性理论学家扬・皮希（Ján Pich）说。他在 2014 年证明了一项关于 PV₁公理能力的重要成果 https://arxiv.org/abs/1412.3246 ，但他也提醒道，反向数学方法最有用的地方或许是揭示研究人员已证明定理之间的新关联，“就目前而言，它对我们尚未知晓如何证明的命题的复杂性，并没有提供太多信息。”

对于元数学研究人员来说，理解这片未知领域仍是一个遥远的目标，但这并未削弱李嘉图对该领域的热情。他于2023年进入麻省理工学院攻读研究生，并最近撰写了一份长达 140 页的复杂性理论学家元数学指南《面向计算机科学家的可行数学与有界算术导论》