OpenAI 攻克唯一博弈猜想：发布 372 项数学成果，AI 证明 NP 难近似极限

昨晚，我9岁的儿子一直在嘲讽我的妻子、复杂性理论家 Dana Moshkovitz：“妈妈，听说你被‘碾压’了！听说有个机器人解决了你毕生研究的数学难题！哎哟！”

虽然儿子表现得有点顽劣，但他说的也没错。无论你是感到兴奋、沮丧、愤怒还是其他情绪，昨天无疑是数学史上最重要的日子之一。是的，在 OpenAI 昨天发布的 372 项重大成果中，根据其由 Timothy Gowers、Edward Witten 及其他杰出数学家组成的 顾问小组 的建议，其中包含了对 Subhash Khot 的 唯一博弈猜想（UGC） 的一个 证明。而 UGC 正是我妻子自我们相识以来一直致力于证明的命题。（UGC 意味着一系列优化问题确实是 NP-hard 的，即使你只想要一个比半定规划松弛——这是我们的主要工具之一——稍好一点的近似解。）

或者至少，我们相当确信这是一个证明！有一个 Lean 证书，就像其他一些（并非全部）突破性的 372 项成果一样。但似乎目前还没有人类真正理解这些证明中的任何一部分；这场理解竞赛才刚刚开始。如果你想了解这场竞赛的实际状况，以下是 Dana 昨晚发给我的部分信息：

感觉像是嗑了迷幻药的人写的。内容含糊不清，毫无逻辑。大量堆砌前人工作的名字，却完全不讨论为何在存在不可能性结果的情况下仍可使用这些工作 基本上，这篇论文写得烂到如果不借助 AI 根本无法阅读 我问 Astra 关于噪声组件（noise gadget）的合理完备性和可靠性声明，它通过整合论文各处的声明给出了答案 他们还提供了针对 UGC 主要应用（最大割问题和所有 CSP）的直接最优 NP 难近似证明，从而绕过了 UGC。 UGC 的证明发明了一种全新的、怪异的编码，并带有噪声测试。这是一种疯狂的递归构造。 既不是长码，也不是短码——简直是外星人的疯狂玩意儿 我仍然认为可能存在一个使用半空间码（half space code，这很自然）的证明 引用往往无关紧要且令人困惑 一种可能的未来是：如果你拥有愿景/创意想法，AI 可以帮你验证和实现，那么数学世界将变得无比美妙。 当然，我们还有很多可以向外星人学习的地方

如果你想知道 Dana 此刻的情绪——好吧，大概全都有！尽管她职业生涯的核心抱负已被机器人取代，但至少有两个因素能让她稍感宽慰。首先，她会感到如释重负，因为 UGC 终究被证实为真，这是她从未怀疑过的，尽管她的许多同事曾对此持疑！其次，我们所有从事数学、理论计算机科学和数学物理的人——至少那些关心解决表述清晰问题的人——如今都身处同一条船上。

---

除了唯一游戏猜想（Unique Games Conjecture），以下是我从阿拉丁神洞中挖掘出的宝藏小样，在接下来的几周里我将重点关注它们：

• L=BPL（即概率对数空间与确定性对数空间等价），这是仅次于 P=BPP 的重大去随机化猜想之一。尽管其真实性从未受到严重质疑，但曾有一整个子社区致力于证明这一结论。

• 傅里叶变换和整数乘法在小于 O(n log n) 的时间内完成，打破了自 1960 年代以来一直存在的壁垒。如果你好奇的话，新的运行时间为 O(n log⁰·⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹ n)，大致如此（取决于具体的 9 的个数）。

• 酉合成问题（Unitary Synthesis Problem）的正向解决方案，该问题由 Greg Kuperberg 和我于 2007 年提出。对于每一个 n 量子比特酉变换 U，都存在一个经典预言机 A，使得 U 可以在访问 A 的情况下以量子多项式时间实现。这与大多数人的预期相反，并可能对例如从黑洞解码霍金辐射的计算问题以及量子复杂性理论中的许多其他问题产生影响——如果我们有一种高效构造预言机 A 的方法，而这篇论文并未提供该方法。

• 奇偶校验函数不属于 QAC0，这是自 1999 年以来量子复杂性理论的重大问题之一，我的许多同事一直在逐步逼近其解决。

• 全布尔函数的随机查询复杂度与量子查询复杂度之间接近四次方的分离。这是我自 1998 年 (!) 以来钟爱的一个问题，当时我们知道最优分离指数介于 2 和 6 之间。在过去几年中，我们知道它介于 3 和 4 之间。因此，这终于为这段历史画上了句号。

• 灵敏度与块灵敏度之间的超二次分离。

• 二维能隙哈密顿量的面积律。这是哈密顿量复杂性领域的主要开放问题之一。

• 一般图中最大匹配问题的随机化近线性时间算法

• 以 $O(n^{9/4})$ 时间进行矩阵乘法——难得出现了一个有理数指数（！），且采用了与 $O(n^{2.373})$ 等结果完全不同的方法

• 永久式行列式复杂度的 $\Omega(n^3)$ 下界，改进了此前最佳的二次方下界。

• 一种用于近似计数一般图中完美匹配数量的随机多项式时间算法，以及一种在此类图中寻找最大匹配的随机近线性时间算法

• 在有理数域上求解多项式方程的不可计算性——这可以说是可计算性理论中最大的开放问题（注：在整数域上求解丢番图方程，即多项式方程的不可计算性已于 1970 年代被证明，从而对希尔伯特第十问题给出了否定答案）

上述任何一项成果，单独拿出来都足以成为某个领域（在某些情况下，如 Unique Games 问题和 L=BPL 问题，甚至整个理论计算机科学领域）的“年度最佳成果”。而且还有很多我未曾提及的内容——欢迎在评论区分享那些让你目瞪口呆的发现！数论、组合数学、代数几何、分析以及几乎所有其他数学领域同样有着令人惊叹的奇迹，尽管其中大部分我永远无法理解。不过我要指出的是，这些进展包括对 黎曼猜想、霍奇猜想 和 BSD 猜想（即剩余千禧年难题中的大多数）的部分突破。

我们可以从清单中缺失的内容中获得些许安慰：P ≠ NP 不在列，甚至连 P=BPP 或 NEXP⊄P/poly 也不在其中，这绝非因为人们没有尝试。显然，理论计算机科学中最伟大的开放性问题确实非常困难！

---

哦，差点忘了：就在 OpenAI 发布结果的前一天，也就是周一晚上，Virginia Williams 和 Josh Alman 在 arXiv 上发布了一篇预印本，以 O(n^1.9992) 的时间复杂度解决了 3SUM 问题，并以 O(n^2.9995) 的时间复杂度解决了所有点对最短路径（All-Pairs Shortest Paths）问题，从而推翻了半个世纪以来认为正确答案分别为 n^{2-o(1)} 和 n^{3-o(1)} 的猜想。在这种情况下，提供关键思路的并非 OpenAI 的模型，而是 Anthropic 的模型！但 Anthropic 采取了与 OpenAI 不同的做法：它没有直接将未经消化的解决方案公之于众，而是给予 Virginia 和 Josh 机会，让他们撰写并公布经过整理的版本，以此作为交换条件提供报酬。

这两种模式已成为传达 AI 数学突破的主要方式，二者各有优劣。“OpenAI 模式”引发了一场人类竞相消化和解释杂乱无章的 AI 证明的疯狂竞赛（这项工作可能既吃力不讨好、鲜少获得认可，又充满竞争且枯燥乏味）；而“Anthropic 模式”则让一家私营公司掌握了挑选哪些人类数学家作为 AI 代言人的权力。我也不确定大家怎么看？

---

对于好奇的人来说：显然，产出这些奇迹的 AI 模型并非由一万个智能体组成的定制装置，也没有消耗价值数百万美元的算力——例如，此前构建纳维-斯托克斯方程有限时间爆破解时曾使用过此类配置。相反，它只是 OpenAI 最新的内部模型之一——根据 OpenAI 安全委员会的建议，该模型可能会在未来几个月内向付费 ChatGPT 用户发布！（我 9 岁的儿子说：“哦，他们绝对不该发布那个。如果它能解决所有那些数学问题，那它不可能是安全的。”）据报道，平均每个解决的问题大约使用了 3 小时的 GPT-Pro 级别算力。

另外，如果你想知道的话：显然他们尝试了约 8,000 个问题。因此，目前它“仅仅”解决了被询问的长期未决数学问题的约 5%——这些问题是整个数学社区耗费数年精力研究的对象，而它只需单次 3 小时的尝试即可解决。

---

我很高兴看到计算机科学理论界积极应对这一挑战。在伯克利的西蒙斯研究所（Simons Institute）、德克萨斯大学奥斯汀分校以及其他地方，我听到研究人员争先恐后地研读手稿，试图理解并解释它们——因为除此之外我们还能做什么呢？否则我们要如何继续从事这项我们倾注了大量生命心血的事业？

如果你想了解当前数学界的感受，不妨想象这样一个场景：一位猎人兼采集者花了一辈子学习如何在严酷的热带雨林深处生存，突然之间，一座带有直升机停机坪、恒温泳池和 Airbnb 民宿的大型度假酒店就在旁边拔地而起。这位猎人兼采集者毫不迟疑地说道：“好吧，行吧，那我现在的任务就是给游客组织野外探险活动之类的。”

在《Quanta》杂志上，Jordana Cepelewitz 尝试了一种不同的比喻：

这就好比把你瞬间传送到了高耸入云的山顶。四周迷雾缭绕，你既不知道自己身在何处，也不清楚周围有什么。你不知道这座山与其他山脉如何相连，手中没有探索所需的装备，也没有办法让其他人加入你的行列。如果你是自己一步步攀登上去的，你就会亲身体验人体如何适应高海拔和氧气含量的变化。你可能不得不发明工具来导航、攀爬陡峭的悬崖或搭建庇护所。你可能会遇到另一位探险者，一起在隐秘的山谷中迷路，并发现一种可以制成救命药物的植物。

然而，此刻你却身处黑暗中的山顶，而那个制造“传送机器”的人却告诉你，这台机器比任何人类都更擅长探索荒野。

对于这些山峰中的任何一座，只要我们足够在意，我乐观地认为我们可以像往常一样行事：拨开迷雾，找出路径——只不过现在我们要借助那台传送机器来指引方向。更大的挑战在于，培育一个社区，让人们依然关心在这个拥有机器的世界里寻找上山之路的英雄主义冒险。（哦，我想这个比喻有一个失效之处：我们彼此之间依然存在联系，就像过去任何时候一样！）

---

经验表明，即便是在当下，仍会有人用居高临下的语气解释为什么这一切都不是真实的，为什么这一切都不算数。如果这些人真的能对现实世界中发生的任何事情感到惊叹，或者能根据任何新信息更新自己的认知，那么早在几年前，在事态发展到真正的“数学末日”（Mathocalypse）之前，他们就已经感到惊叹并更新了认知了。

因此，他们会说，也许那些所谓的解决方案根本不是解决方案，只是“AI 垃圾内容”（AI slop）。或者，也许那 372 个被解决的著名开放问题并不是真正的数学问题，它们全都只是包装精美的竞赛谜题和琐碎小事。（毕竟，黎曼猜想还没被解决嘛！）又或者，整个有着 4000 年历史的数学学科都需要被抛弃：事实证明，它全部都只是解谜游戏和琐碎之事；唯一的区别是，如今这种琐碎性不再被掩盖而已。无论如何，真正重要的是，人类创造力的真正核心圣殿尚未被攻破，而且可能永远不会被攻破；此外，Sam Altman 和 Dario Amodei 都是令人鄙视的书呆子。

如果你仍然坚持那种注定失败的世界观，仍然身处这艘正在沉没的船上，我强烈建议你阅读昨天 AI 讨论领域的另一篇重磅文章——除了 OpenAI 发布的“数学末日”（Mathocalypse）报告之外：即 Scott Alexander 致 Steven Pinker 的公开信。对此我深感责任重大，因为是我首先向 Steven Pinker 介绍了理性主义社区的存在，也是我先让 Steven Pinker 和 Scott Alexander 相识（他们此前都欣赏对方的作品）。而现在，Scott 竟然向 Steve 发起了字面意义上的决斗，还要动枪！

仅供参考：Steve 是我毕生的智力偶像，正如他是 Scott 的偶像一样；我也有幸称 Steve 为朋友。但我认为 Scott 的文章是我读过的最具毁灭性的反驳之一。而且我觉得 Scott 的结论完全正确：在 AI 风险问题上，Steve 面临的巨大挑战是接受并开始使用一种更“Pinker 式”的认识论。

---

昨晚，本应埋头研读 OpenAI 那数百篇论文中的一小部分，或者撰写这篇博文，我却决定花些时间陪陪孩子。他们想看电影，于是我提议看一部他们从未见过、而我也几十年没看过的片子，并且觉得其中充满了在他们即将成长的世界里所需的务实指导：《终结者 2》。

本文发布于 2026 年 10 月 7 日星期三下午 1，分类于 Uncategorized。你可以通过 RSS 2.0 订阅跟踪此条目的任何回复。你可以留下评论，或从你自己的网站发送 trackback。