OpenAI 宣称证明 unique games 猜想，MIT 团队抢先发布 95 页论文

在传闻中人工智能证明其领域最大难题之一的阴影下，三位计算机科学家匆忙发表了他们自己的里程碑式成果。

引言

2026年9月11日早晨，Dor Minzer收到一位朋友发来的短信，问他是否即将解决理论计算机科学中最著名的未解问题之一。Minzer是麻省理工学院的教授，也是“唯一游戏”猜想领域的顶尖专家，起初他以为这是个玩笑。随后更多消息接踵而至，传言开始变得清晰起来。人工智能公司OpenAI刚刚宣布了一项关于流体行为的重磅证明，在数学界引起轩然大波，据称他们又发现了唯一游戏猜想的证明。他们可能随时会公布这一结果。这些消息暗示，如果Minzer自己有什么成果要分享，现在正是时候。

唯一游戏猜想是计算复杂性理论中的一个标志性问题，该理论研究数学问题的内在难度。粗略地说，它指出一个关于同时满足多个约束的问题可能极其困难，即使你愿意接受对最优解的粗略近似。该猜想的证明还将自动意味着，当前用于解决许多看似无关问题的方法无法再改进。研究人员将朝着计算难度的统一理论迈出一大步。

事实上，Minzer并没有证明唯一游戏猜想。但他和他的研究生Yumou Fei和Shuo Wang最近证明了一个与密切相关问题的里程碑式结果。当传言开始流传时，他们正在撰写论文——这一过程通常需要数月甚至更长时间。三人加紧完成草稿，以免被OpenAI的新闻稿抢了风头。三天后，他们优先考虑完整性而非清晰度，在网上发布了一篇95页的论文，首页附有免责声明：“当前版本的手稿在数学上是完整的，但并非我们希望分享的形式。”

他们迅速发表的决定很快得到了证实。10月6日，OpenAI宣布了唯一游戏猜想的证明，以及跨越数学多个不同领域的376项其他结果。研究人员对大量人工智能证明的反应是既警觉又好奇，这在近期进展之后已变得司空见惯。他们对Minzer成果的反应则不那么矛盾。

“他在这个主题上发表了许多出色的论文，”卡内基梅隆大学的理论计算机科学家Ryan O’Donnell说。“这是又一篇真正伟大的论文。”

基本满意

唯一游戏猜想和该团队新成果的核心问题都涉及同时满足许多可能相互冲突的约束。类似的问题在日常生活中也会出现：例如填写数独谜题，或为婚礼安排座位。（你会希望把朋友安排在一起，同时确保不和的客人被分配到不同的桌子——而且你还得填满每张桌子的所有座位。）

精确求解约束满足问题可能很困难，甚至不可能。有时，存在一个满足所有约束的解，但所有已知的求解方法都慢得令人痛苦。或者约束之间可能相互冲突，完美的解根本不存在。

在这些情况下，研究人员往往愿意退而求其次，接受满足部分而非全部约束的近似解。复杂性理论家想要理解为什么寻找这些近似解有时容易、有时困难。“大量工作都致力于试图弄清楚边界在哪里，”奥唐奈说。

唯一游戏猜想与这一探索密切相关，它最早由复杂性理论家苏巴什·科特在还是研究生时于2002年的一篇论文中提出。该猜想涉及一个特定的约束满足问题，关于被称为图的数学对象，图是由称为边的线连接起来的节点网络。给定一个图，要求你使用固定的调色板为其节点着色。每条边都附带一条规则，决定两端节点应该是什么颜色。例如，某条特定的边可能要求两个节点颜色相同。另一条边可能要求如果一个节点是红色，另一个必须是蓝色；如果一个节点是绿色，另一个必须是黄色。

这个着色问题的难度取决于图的布局、允许的颜色数量以及具体的约束集合。科特感兴趣的是那些最佳着色满足大多数但并非全部约束的情况——比如99%的约束。找到这种近乎完美的着色是一项艰巨的任务。直觉上，找到一个满足较小比例约束的着色似乎更容易——1%甚至0.001%的约束。

唯一游戏猜想认为这种直觉是错误的。无论你愿意把标准放宽多少，总会有一些情况，即使这些次等的着色也难以找到。

唯一游戏猜想提出了一个惊人的论断，但其真正价值在于它与其他问题的联系。研究人员利用这一猜想攻击看似无关的问题，涉及泡沫的几何结构和投票系统的性质。2008年，计算机科学家普拉萨德·拉加文德拉证明了如果该猜想成立，那么对于所有不存在完美解的约束满足问题，某个经典算法就是最佳策略。你无法通过利用特定问题的特殊之处做得更好。

然而，该猜想有一个盲点。它只适用于最佳可能解满足大多数约束的情况，比如上述99%的情况。对于存在完美解——即100%的约束都能被满足——的情况，它没有说明。

科特从一开始就认识到了这一局限。为了解决这些情况，他定义了唯一游戏问题的一个变体，称为2对1游戏问题，其中约束更为宽松。在原问题中，为边一侧的节点着色必须使另一侧的颜色只有一个选项。在新版本中，他允许有两种可能的颜色。

他推测，对于这个问题，在某些情况下，最优解能满足所有约束，但仍然很难找到满足哪怕极小一部分约束的解。证明这个鲜为人知的猜想，也将意味着关于许多其他问题的结果，而这些并不属于唯一游戏猜想这一范畴。

在9月份的论文中，Minzer及其同事证明了Khot第二个猜想的一个轻微变体，其后果几乎相同。对Minzer来说，这项工作历时七年。

一连串的失败

2018年，当时还是研究生的Minzer在一个著名成果中发挥了主导作用，该成果标志着朝着证明Khot的两个猜想迈出了第一个重大进展。但他的进展最终停滞了。然后，在2025年，他与Fei和Wang讨论了2对1问题，这两人刚读完研究生一年级，并完成了一次成果丰硕的首次合作。

“我给了他们两个问题选项，”Minzer说。“他们足够勇敢，选择了这一个。”

要解决这个猜想，三人需要搭建一座数学桥梁，从2对1问题通向另一个难度已被充分理解的问题。在Minzer之前的工作中，搭建这座桥梁的第一步涉及将图着色问题转化为一个关于“纠错码”的问题，纠错码是一种对消息进行编码的方法，使接收者能够检测并修复传输错误。

几个月后，Fei和Wang找到了一种有前景的新方法来构建纠错码。但他们看不出如何将这些新编码与搭建桥梁所需的所有其他部分结合起来。

“看起来非常渺茫，”Minzer说。“你需要奇迹发生，所有星星都排成一线。”

在那之后的几个月里，星星并没有排成一线。三人反复尝试让证明成立，但都失败了，而拼凑这些部分感觉“就像试图把圆形和三角形拼进同一个拼图里，”Fei说。然而，他们从每一次受挫的尝试中都学到了东西。2026年4月，他们终于成功了。

“我们经历了五次失败，并设法把这个[新编码]钉在它们上面，”Minzer说。“然后它就奏效了。”

严格来说，Minzer、Fei和Wang证明的是Khot的2对1游戏猜想的一个稍弱版本，其中每个约束有四个选项而非两个。但Khot原始猜想的许多推论已经可以从这个4对1版本中得出——最值得注意的是，一个关于经典图着色问题难度的新结果，而这个问题比Khot的工作早了几十年。在这个著名问题中，唯一的约束是相邻节点不能有相同的颜色。复杂性理论家早就知道，在可以用三种颜色给给定图着色的情况下，这样的解可能极难找到。Minzer、Fei和Wang的新结果现在也意味着，在这些情况下，无论你被允许使用多少额外颜色，总会有一些反常的图，仍然很难找到解。

“即使有整盒Crayola蜡笔，你也做不到，”普林斯顿大学的Mark Braverman说。计算机科学家几十年来一直试图证明这一结果——事实上，这正是最初促使Khot提出他的图着色猜想的问题之一。

OpenAI 十月的发布包含了一个Lean 验证的 2 比 1 猜想的证明，但该证明出自一份 AI 生成的手稿，未经任何人工编辑或独立专家评审。这并不意味着那份为赶在 OpenAI 发布之前而匆忙完成的九月 4 比 1 结果就完美无缺。

“从第 6 节开始，字面上没有任何连接词，”Minzer 说——只有一连串不间断的定义和中间结果的证明。“我们觉得有必要为此道歉。”

该团队计划在完成充实后发布论文的新版本。但在 AI 辅助写作日益普及的时代，这份明显未经润色的文本自有其魅力。正如 O'Donnell 所说：“他们用老派的方式解决了问题，用他们的头脑，用他们自己的手指写出来。”

成功的代价

然后是 OpenAI 对唯一游戏猜想的证明，这绝非老派。这是迄今为止理论计算机科学领域最引人注目的 AI 生成证明——这还包括 OpenAI 同时发布的另外 40 个理论计算机科学证明。

研究人员要消化的东西很多。“通过新闻稿发布数学对数学并不健康，”Braverman 在九月被问及即将到来的 OpenAI 公告的传闻时说。“我们已经经历了很多不确定性和不愉快。”不过，他指出，AI 生成的该猜想证明可能为研究人员开辟新的探索方向。如果他们能梳理出证明中的关键假设——对于 AI 生成的证明来说这并不总是容易的事——他们或许能通过调整这些假设并探索结果如何变化来学到很多。“这不是‘一劳永逸’，”他说。

数学和理论计算机科学领域的一些研究人员通过采用 AI 工具进行自己的研究，来应对 AI 能力的快速进步。就 Minzer 而言，他担心这些新工具正在如何改变研究过程。他的新成果的故事就是一个例证。“失败并知道为什么失败很有价值，”他说。“使用 AI 把这一切都抹去了。”

他还担心 AI 的进步会让研究人员不愿追求雄心勃勃的长期项目。

“你是人类，对吧？你需要睡觉，需要吃饭，有情绪，”他说。“你不知道自己会不会被那家万亿美元公司抢先。”