"逆向数学"揭示难题为何如此之难
在逆向数学中，研究者们用他们想要证明的定理来替换公理——这些公理是数学体系的基础。
原文：https://www.quantamagazine.org/reverse-mathematics-illuminates-why-hard-problems-are-hard-20251201/
作者：Ben Brubaker
译者：Kurt Pan
引言
说到难题，计算机科学家们似乎陷入了困境。以一个臭名昭著的问题为例：寻找一条经过地图上每座城市恰好一次的最短往返路线。所有已知的解决这个"旅行商问题"的方法在城市数量较多时都极其缓慢，研究者们怀疑没有更好的办法。但没有人知道如何证明这一点。
https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/
五十多年来，计算复杂性理论领域的研究者们一直试图将"旅行商问题是困难的"这类直觉性陈述转化为无懈可击的数学定理，但收效甚微。他们也越来越多地寻求对一个相关且更加模糊的问题的严格解答：为什么他们的证明没有成功？
https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/
这项将数学证明过程本身作为数学分析对象的工作，属于一个以令人望而生畏著称的领域——元数学。元数学家们经常审视作为所有证明起点的基本假设，即公理。他们改变所使用的公理，然后探索这些改变如何影响他们能够证明哪些定理。当研究者们使用元数学来研究复杂性理论时，他们试图勾勒出不同的公理集合能够和不能证明关于计算难度的哪些内容。他们希望这样做能帮助他们理解为何在证明问题困难性方面一直未能取得突破。
在去年发表的一篇论文中，三位研究者对这一挑战采取了新的方法。他们颠倒了数学家们使用了数千年的范式：他们不再从一套标准公理出发来证明定理，而是用一个定理替换掉其中一条公理，然后证明那条公理。他们使用这种称为逆向数学的方法，证明了复杂性理论中许多不同的定理实际上是完全等价的。
https://eccc.weizmann.ac.il/report/2024/060/
"我很惊讶他们能够完成这么多工作，"IBM的复杂性理论学家 Marco Carmosino 说。"人们会看到这个然后说，'这就是让我进入元数学领域的契机。'"
鸽巢证明
这篇逆向数学论文的故事始于2022年夏天，当时 Lijie Chen——现任加州大学伯克利分校的复杂性理论学家——正在完成他的博士学位。他发现自己有大量空闲时间，于是决定花几个月阅读元数学方面的资料。
"因为我即将毕业，没有太多研究要做，"Chen 说。"我想我应该学些新东西。"
在阅读过程中，Chen 开始思考复杂性理论的一个分支——通信复杂性，该分支研究两个或多个人为完成某些任务必须交换的信息量。通信复杂性中最简单的问题之一叫做"相等性问题"，类似于一个协作游戏。两名玩家各自拥有一串由0和1（即比特）组成的字符串。他们的目标是用尽可能少的通信来确定他们的字符串是否相同。最简单的策略是让一名玩家直接发送完整的字符串供另一名玩家核对。有没有更好的办法？
复杂性理论学家们几十年前就证明了答案是否定的。要解决相等性问题，玩家至少需要发送与完整字符串中比特数相等的比特数。理论学家们称这个字符串长度是所需通信量的"下界"。
Chen 关注的并非相等性问题下界本身——他感兴趣的是研究者们如何证明它。所有已知的证明都依赖于一个简单的定理，称为鸽巢原理，该原理指出，如果你把若干只鸽子放进数量更少的笼子里，至少有一个笼子最终会容纳不止一只鸟。这听起来可能不言自明，但它在复杂性理论及其他领域中可以是一个出人意料的强大工具。
https://www.quantamagazine.org/how-a-problem-about-pigeons-powers-complexity-theory-20250404/
Chen 发现了一个诱人的线索，表明相等性问题与鸽巢原理之间的联系可能也是双向的。用鸽巢原理来证明相等性问题的下界很容易。但你能否反过来用这个下界来证明鸽巢原理呢？
不可思议的等价性
Chen 与 Jiatu Li 讨论了他的想法。Li 当时是清华大学的本科生，Chen 最近刚与他在另一篇论文上有过合作。为了使这种联系严格化，他们需要选择一套公理来进行研究。元数学研究者们倾向于使用比通常更为受限的公理。这些较弱的公理使得精确确定不同定理之间的关系变得更加容易。Chen 和 Li 决定使用一套流行的公理集，称为 。 本身就足够强，能够独立证明一些关于计算复杂性的重要定理。加入鸽巢原理的一个特定版本作为额外公理，你还可以证明相等性问题的下界。2022年12月，Li 和 Chen 正式证明了，正如 Chen 所怀疑的那样，将两个定理互换后证明同样成立。
https://dl.acm.org/doi/10.1145/800116.803756
你可以从鸽巢原理证明相等性问题的下界，反之亦然，这一事实意味着在 的逻辑框架内，这两个定理是完全等价的。当 Li 和 Chen 与华威大学的复杂性理论学家 Igor Oliveira 讨论这一结果时，三人意识到他们的逆向数学方法可能也适用于复杂性理论其他遥远领域的定理。在接下来的几个月里，他们系统地证明了许多其他定理之间的等价性。
"一开始，我们只有两个等价的东西，"Chen 说。"但现在我们有了一张巨大的关系网。"
该团队最引人注目的联系将同一版本的鸽巢原理与学生在计算复杂性理论入门课程中最先遇到的定理之一联系起来。正如 Carmosino 所描述的，这个"经典定理"为一种称为单带图灵机的理论计算机确定一串0和1是否为回文（即正读和反读相同）所需的时间设定了下界。Li、Chen 和 Oliveira 使用逆向数学证明了在 内，这个回文下界定理与鸽巢原理是等价的。
https://www.quantamagazine.org/alan-turings-most-important-machine-was-never-built-20230503/
"如果你告诉我这个，我不会相信，"Chen 说。"这听起来非常荒谬。"
回文下界与鸽巢原理之间的等价性令人惊讶，因为这两个定理表面上差异如此之大。鸽巢原理本质上与计算无关：它只是一个关于计数的简单陈述。而回文下界则是关于特定计算模型的陈述。这一新结果表明，这类看似狭隘的定理实际上比它们表面呈现的更为普适。
"这表明我们想要理解的这些复杂性下界要基本得多，"Oliveira 说。
未知领域
这张新的等价性关系网也帮助揭示了 的局限性。研究者们此前已有理由相信，仅凭 的公理无法证明鸽巢原理，因此 Li、Chen 和 Oliveira 的结果暗示，他们证明等价的其他定理在 中可能同样无法证明。
"我认为这很美，"牛津大学的复杂性理论学家 Ján Pich 说，他在2014年证明了一个关于 能力的重要结果。但他提醒说，逆向数学方法可能最适合揭示研究者们已经证明的定理之间的新联系。"就我们目前所知，它并没有告诉我们太多关于那些我们还不知道如何证明的陈述的复杂性。"
理解这片未知领域对元数学研究者来说仍是一个遥远的目标。但这并没有削弱 Li 对这一学科的热情。他于2023年开始在麻省理工学院攻读研究生，最近还为复杂性理论学家撰写了一份140页的元数学指南。这是一个更广泛趋势的例证：在相对默默无闻数十年之后，元数学正越来越多地吸引更广泛研究者群体的关注，他们为这一领域带来了新的视角。
https://eccc.weizmann.ac.il/report/2025/086/
"人们已经厌倦了停滞不前，"Carmosino 说。"是时候退后一步，把基础搞清楚了。"