As AI Closed In on ‘Unique Games’ Proof, Researchers Raced to Beat the Machines

On the morning of September 11, 2026, Dor Minzer received a text message from a friend asking whether he was close to settling one of the most famous open questions in theoretical computer science.

2026 年 9 月 11 日上午，Dor Minzer 收到一位朋友发来的短信，询问他是否即将解决理论计算机科学领域最著名的开放问题之一。

Minzer, a professor at the Massachusetts Institute of Technology and a leading expert on the “unique games” conjecture, initially thought it was a joke.

麻省理工学院教授、“独特游戏”猜想的权威专家明泽最初认为这是一个笑话。

Then more messages started coming in, and the rumors began to cohere.

然后更多的消息开始传来，谣言开始连贯起来。

The artificial intelligence company OpenAI, fresh from announcing a bombshell proof about the behavior of fluids that sent ripples through the math world , had allegedly discovered a proof of the unique games conjecture.

人工智能公司 OpenAI 刚刚宣布了有关流体行为的爆炸性证据，在数学界引起了轩然大波，据称已经发现了独特游戏猜想的证明。

They might make the result public any day.

他们可能随时会公开结果。

If Minzer had any results of his own to share, the messages suggested, now would be the time to do so.

消息显示，如果明泽有任何自己的成果可以分享，那么现在就是这样做的时候了。

The unique games conjecture is an iconic question in computational complexity theory, the study of the inherent difficulty of mathematical problems.

独特博弈猜想是计算复杂性理论中的一个标志性问题，计算复杂性理论研究数学问题的固有难度。

Roughly speaking, it states that a problem about satisfying multiple constraints at the same time can be extremely hard, even if you’re willing to settle for a poor approximation of the best possible solution.

粗略地说，它指出同时满足多个约束的问题可能非常困难，即使您愿意接受最佳可能解决方案的较差近似。

A proof of the conjecture would also automatically imply that current methods for solving many seemingly unrelated problems can’t be improved.

该猜想的证明也自动意味着当前解决许多看似不相关问题的方法无法得到改进。

Researchers would be a big step closer to a unified theory of computational difficulty.

研究人员将向统一计算难度理论迈进一大步。

Minzer had not, in fact, proved the unique games conjecture.

事实上，明泽并没有证明独特的博弈猜想。

But he and his graduate students Yumou Fei and Shuo Wang had recently proved a milestone result about a closely related question.

但他和他的研究生余谋费和王硕最近在一个密切相关的问题上证明了一个里程碑式的结果。

They were in the midst of writing up their findings — a process that would typically take months or longer — when the rumors began circulating.

当谣言开始流传时，他们正在写下他们的发现——这个过程通常需要几个月或更长时间。

The trio rushed to finish their draft to avoid being overshadowed by an OpenAI press release.

三人匆忙完成了草稿，以避免被 OpenAI 新闻稿的光芒掩盖。

Three days later, prioritizing completeness over clarity, they posted a 95-page paper online with a disclaimer on the first page: “The current version of the manuscript is complete mathematically, but it is not in the shape we wished to share in.”

三天后，他们优先考虑完整性而不是清晰度，在网上发布了一篇 95 页的论文，并在第一页上有免责声明：“手稿的当前版本在数学上是完整的，但它不是我们希望分享的形式。”

Dor Minzer and his students recently rushed to post a milestone result in theoretical computer science, hoping to avoid being upstaged by a rumored AI proof.

多尔·明泽 (Dor Minzer) 和他的学生最近急于发布理论计算机科学领域的一项里程碑式成果，希望避免被传闻中的人工智能证明抢了风头。

Their decision to publish quickly was soon vindicated.

他们迅速发表的决定很快就得到了证实。

On October 6, OpenAI announced a proof of the unique games conjecture, along with 376 other results across many different fields of math.

10 月 6 日，OpenAI 宣布了独特游戏猜想的证明，以及许多不同数学领域的 376 个其他结果。

Researchers greeted the deluge of AI proofs with the mixture of alarm and curiosity that has become familiar in the wake of recent advances.

研究人员对人工智能证据的泛滥感到震惊和好奇，随着最近的进展，这种情绪已经变得司空见惯。

Their reaction to Minzer’s result was less ambivalent.

他们对明泽结果的反应不那么矛盾。

“He’s put out many great papers on this topic,” said Ryan O’Donnell , a theoretical computer scientist at Carnegie Mellon University.

卡内基梅隆大学理论计算机科学家瑞安·奥唐纳 (Ryan O’Donnell) 表示：“他在这个主题上发表了许多精彩的论文。”

“This is another truly great one.”

“这是另一件真正伟大的事情。”

The problems at the heart of both the unique games conjecture and the team’s new result are about simultaneously satisfying many constraints that may be in tension with each other.

独特的游戏猜想和团队的新结果的核心问题是同时满足许多可能相互矛盾的约束。

Similar problems arise in everyday life: filling in a sudoku puzzle, for instance, or planning seating arrangements for a wedding.

日常生活中也会出现类似的问题：例如，填写数独游戏，或规划婚礼的座位安排。

(You’ll want to seat friends together, while making sure that guests who don’t get along are assigned to different tables — and you’ll have to fill all the seats at each table.)

（你会想把朋友们安排在一起，同时确保不合群的客人被分配到不同的桌子上——而且你必须把每张桌子上的所有座位都坐满。）

Solving constraint satisfaction problems exactly can be hard or even impossible.

准确地解决约束满足问题可能很困难，甚至是不可能的。

Sometimes, there is a solution that satisfies every constraint, but all known methods for finding that solution are painfully slow.

有时，有一个解决方案可以满足所有约束，但所有已知的找到该解决方案的方法都非常缓慢。

Or the constraints might conflict with each other, and a perfect solution simply doesn’t exist.

或者这些约束可能会相互冲突，并且根本不存在完美的解决方案。

In these cases, researchers are often willing to settle for approximate solutions that satisfy some but not all of the constraints.

在这些情况下，研究人员通常愿意满足一些但不是全部约束的近似解决方案。

Complexity theorists want to understand why it’s sometimes easy and sometimes hard to find these approximate solutions.

复杂性理论家想要理解为什么找到这些近似解有时很容易有时很难。

“A lot of work has been devoted to trying to figure out where is the boundary,” O’Donnell said.

“我们做了很多工作来试图找出边界在哪里，”奥唐纳说。

The unique games conjecture, first articulated in a 2002 paper by the complexity theorist Subhash Khot when he was still a graduate student, is intimately connected to that quest.

复杂性理论家 Subhash Khot 在 2002 年的一篇论文中首次提出了独特的博弈猜想，当时他还是一名研究生，它与这一探索密切相关。

It concerns a specific constraint satisfaction problem about mathematical objects called graphs, which are networks of nodes connected by lines called edges.

它涉及有关称为图的数学对象的特定约束满足问题，图是由称为边的线连接的节点网络。

You’re given a graph and asked to color its nodes using a fixed color palette.

给你一个图表，并要求你使用固定的调色板为其节点着色。

Each edge comes with a rule that determines what color the nodes at either end should be.

每条边都有一个规则，用于确定两端的节点应该是什么颜色。

For instance, one particular edge might require that the two nodes have the same color.

例如，一条特定的边可能要求两个节点具有相同的颜色。

Another edge might demand that if one node is red, the other must be blue, and that if one node is green, the other must be yellow.

另一条边可能要求如果一个节点是红色，则另一个节点必须是蓝色，如果一个节点是绿色，则另一个节点必须是黄色。

Subhash Khot posed the unique games conjecture back when he was still in graduate school.

Subhash Khot 在读研究生时就提出了独特的博弈猜想。

The difficulty of this coloring problem will depend on the layout of the graph, the number of allowed colors, and the specific set of constraints.

此着色问题的难度取决于图形的布局、允许的颜色数量以及特定的约束集。

Khot was interested in cases where the best possible coloring satisfies most but not all of the constraints — say, 99% of them.

Khot 对最佳着色能够满足大多数但不是全部约束（例如 99%）的情况感兴趣。

Finding this near-perfect coloring is a difficult task.

找到这种近乎完美的色彩是一项艰巨的任务。

Intuitively it would seem easier to find a coloring that satisfies a smaller fraction of the constraints — 1% or even 0.001% of them.

直觉上，找到一种满足较小比例约束的颜色似乎更容易——1% 甚至 0.001%。

The unique games conjecture says that this intuition is wrong.

独特博弈猜想说，这种直觉是错误的。

No matter how much you’re willing to relax your standards, there will always be cases where even these subpar colorings are hard to find.

无论你多么愿意放宽你的标准，总会有这样的情况，即使是这些低于标准的颜色也很难找到。

The unique games conjecture makes a striking claim, but its real value lies in its connections to other problems.

独特的博弈猜想提出了一个引人注目的主张，但其真正的价值在于它与其他问题的联系。

Researchers have used the conjecture to attack apparently unrelated questions about the geometry of foams and the properties of voting systems .

研究人员利用这一猜想来解决有关泡沫几何形状和投票系统特性的明显不相关的问题。

And in 2008, the computer scientist Prasad Raghavendra proved that if the conjecture is true , one particular classic algorithm is the best strategy for every constraint satisfaction problem where no perfect solution exists.

2008 年，计算机科学家 Prasad Raghavendra 证明，如果这个猜想成立，那么一种特定的经典算法是解决每个不存在完美解决方案的约束满足问题的最佳策略。

You can’t do better by exploiting the quirks of specific problems.

你无法通过利用特定问题的怪癖来做得更好。

They solved the problem in the old-fashioned way, with their minds, and wrote it with their own fingers.

他们用老式的方式解决问题，用自己的头脑，用自己的手指写出来。

Ryan O’Donnell, Carnegie Mellon University

瑞安·奥唐纳，卡内基梅隆大学

Yet the conjecture has a blind spot.

然而这个猜想有一个盲点。

It only applies to cases where the best possible solution satisfies most constraints, such as the 99% case above.

它仅适用于最佳可能解决方案满足大多数约束的情况，例如上面的 99% 情况。

It says nothing about cases where there’s a perfect solution — where 100% of the constraints can be satisfied.

它没有提到存在完美解决方案的情况——可以满足 100% 的约束。

Khot recognized this limitation from the beginning.

科特从一开始就意识到了这一局限性。

To address those cases, he defined a variant of the unique games problem called the 2-to-1 games problem, in which the constraints are looser.

为了解决这些情况，他定义了独特博弈问题的一个变体，称为 2 对 1 博弈问题，其中的约束更为宽松。

In the original problem, coloring a node on one side of an edge must leave only one option for the color on the other side.

在最初的问题中，对边一侧的节点进行着色必须只为另一侧的颜色留下一个选项。

In the new version, he allowed for two possible colors.

在新版本中，他允许使用两种可能的颜色。

For this problem, he conjectured, there are cases where the best possible solution satisfies all constraints, but it’s still hard to find a solution that satisfies any tiny fraction.

他推测，对于这个问题，在某些情况下，最好的解决方案可以满足所有约束条件，但仍然很难找到满足任何微小分数的解决方案。

A proof of this lesser-known conjecture would also imply results about a host of other problems that don’t fall under the umbrella of the unique games conjecture.

这个鲜为人知的猜想的证明也意味着许多其他问题的结果，这些问题不属于独特博弈猜想的范畴。

In their paper from September, Minzer and his colleagues proved a slight variant of Khot’s second conjecture that has nearly the same consequences.

在 9 月份的论文中，明泽和他的同事证明了科特第二个猜想的一个微小变体，其结果几乎相同。

For Minzer, the work was seven years in the making.

对于明泽来说，这部作品的制作花了七年时间。

In 2018, while still a graduate student, Minzer played a leading role in a celebrated result marking the first significant advance toward proving Khot’s two conjectures.

2018 年，当明泽还是一名研究生时，他在一项著名的结果中发挥了主导作用，标志着证明科特的两个猜想的第一个重大进展。

But his progress eventually stalled.

但他的进步最终停滞了。

Then, in 2025, he discussed the 2-to-1 problem with Fei and Wang, who had just finished their first year of graduate school and wrapped up a fruitful first collaboration.

然后，在 2025 年，他与刚刚完成研究生一年级的费和王讨论了 2 对 1 的问题，结束了一次富有成效的第一次合作。

“I gave them two options of which problem to choose,” Minzer said.

“我给了他们两个选择，选择哪个问题，”明泽说。

“They were brave enough to choose this one.”

“他们有足够的勇气选择这个。”

To settle the conjecture, the trio would need to build a mathematical bridge from the 2-to-1 problem to another problem whose difficulty was already well understood.

为了解决这个猜想，三人需要建立一座从 2 对 1 问题到另一个问题的数学桥梁，而这个问题的难度已经被很好地理解了。

In Minzer’s previous work, the first step in building that bridge involved transforming the graph-coloring problem into a problem about “error-correcting codes,” a method for encoding messages so that a recipient can detect and fix transmission errors.

在 Minzer 之前的工作中，构建这座桥梁的第一步是将图形着色问题转化为“纠错码”问题，“纠错码”是一种对消息进行编码的方法，以便接收者能够检测并修复传输错误。

After a few months, Fei and Wang identified a promising new approach to building error-correcting codes.

几个月后，费和王发现了一种有前途的构建纠错码的新方法。

But they couldn’t see how to combine those new codes with all the other pieces that needed to go into the bridge.

但他们不知道如何将这些新代码与需要进入桥梁的所有其他部分结合起来。

“It looked very remote,” Minzer said.

“它看起来非常遥远，”明泽说。

“You needed miracles to happen, all of the stars to align.”

“你需要奇迹的发生，所有的星星都对齐。”

For months after that, the stars did not align.

在那之后的几个月里，星星并没有对齐。

The trio repeatedly tried and failed to make the proof work, but assembling the pieces felt “like trying to fit a circle and a triangle together in a jigsaw puzzle,” Fei said.

费说，三人多次尝试证明，但都失败了，但组装这些碎片感觉“就像试图将一个圆形和一个三角形拼成拼图游戏”。

Yet they learned something from each thwarted attempt.

然而，他们从每一次失败的尝试中都学到了一些东西。

In April 2026, they finally succeeded.

2026年4月，他们终于成功了。

“We took five failures and managed to staple this [new code] on top of them,” Minzer said.

“我们经历了五次失败，并设法将这个[新代码]钉在上面，”明泽说。

“And then it worked.”

“然后就成功了。”

Technically, Minzer, Fei, and Wang proved a slightly weaker version of Khot’s 2-to-1 games conjecture, in which there are four options for each constraint rather than two.

从技术上讲，Minzer、Fei 和 Wang 证明了 Khot 2 对 1 博弈猜想的一个稍弱的版本，其中每个约束有四个选项，而不是两个。

But many of the implications of Khot’s original conjecture already followed from this 4-to-1 version — most notably, a new result about the difficulty of a classic graph-coloring problem that predates Khot’s work by decades.

但科特最初猜想的许多含义已经从这个 4 比 1 版本中得到了体现——最值得注意的是，关于经典图形着色问题的难度的新结果比科特的工作早了几十年。

In this famous problem, the only constraint is that adjacent nodes can’t have the same color.

在这个著名的问题中，唯一的限制是相邻节点不能具有相同的颜色。

Complexity theorists have long known that in cases where it’s possible to color a given graph with just three colors, such a solution can be prohibitively difficult to find.

复杂性理论家早就知道，如果可以只用三种颜色给给定的图着色，那么找到这样的解决方案可能会非常困难。

Minzer, Fei, and Wang’s new result now also implies that in these cases, no matter how many extra colors you’re allowed to use, there will always be perverse graphs where it’s still hard to find a solution.

Minzer、Fei 和 Wang 的新结果现在还意味着，在这些情况下，无论允许使用多少额外颜色，总会出现反常的图形，仍然很难找到解决方案。

Shuo Wang (top) and Yumou Fei used an exotic error-correcting code to make their new proof work where others had failed.

王硕（上）和费于谋使用了一种奇特的纠错码，使他们的新证明在其他人失败的地方发挥作用。

“You cannot do it even with the entire Crayola box,” said Mark Braverman of Princeton University.

普林斯顿大学的马克·布雷弗曼 (Mark Braverman) 表示：“即使使用整个绘儿乐盒子，你也无法做到这一点。”

Computer scientists had sought to prove this result for decades — in fact, it was one of the problems that originally motivated Khot to propose his graph-coloring conjectures.

几十年来，计算机科学家一直试图证明这个结果——事实上，这是最初促使科特提出图形着色猜想的问题之一。

OpenAI’s October release included a Lean-verified proof of the 2-to-1 conjecture, but in an AI-generated manuscript that didn’t undergo any human editing or review by independent experts.

OpenAI 10 月份发布的版本包括经过精益验证的 2 比 1 猜想证明，但采用的是人工智能生成的手稿，未经过任何人工编辑或独立专家的审查。

Not that the September 4-to-1 result, which was rushed to predate the OpenAI dump, is in perfect shape.

这并不是说 9 月 4 比 1 的结果是在 OpenAI 转储之前仓促做出的，它的状态是完美的。

“From section 6 onward, there are literally no connecting words,” Minzer said — just an unbroken sequence of definitions and proofs of intermediate results.

“从第 6 节开始，实际上就没有任何连接词了，”明泽说，只有不间断的定义序列和中间结果的证明。

“We felt the need to apologize for that.”

“我们觉得有必要为此道歉。”

The team plans to post a new version of their paper when they’ve finished fleshing it out.

该团队计划在充实完善后发布论文的新版本。

But in an age where AI-assisted writing is becoming increasingly ubiquitous, the distinctly unpolished text has its own charm.

但在人工智能辅助写作变得越来越普遍的时代，明显未经修饰的文本也有其自身的魅力。

As O’Donnell put it, “They solved the problem in the old-fashioned way, with their minds, and wrote it with their own fingers.”

正如奥唐纳所说，“他们用老式的方式解决了问题，用自己的头脑，用自己的手指写出来。”

Then there’s OpenAI’s proof of the unique games conjecture, which is anything but old-fashioned.

然后是 OpenAI 对独特游戏猜想的证明，这绝不是过时的。

It’s the highest-profile example of an AI-generated proof in theoretical computer science to date — and that’s including the 40 other theoretical computer science proofs that OpenAI released at the same time.

这是迄今为止理论计算机科学领域最引人注目的人工智能生成证明的例子，其中包括 OpenAI 同时发布的其他 40 个理论计算机科学证明。

It’s a lot for researchers to take in.

研究人员需要考虑的内容有很多。

“Math by press release is not that healthy for math,” Braverman said in September, when asked about the rumors of an upcoming OpenAI announcement.

“新闻稿中的数学对数学来说并不那么健康，”布雷弗曼在 9 月份被问及有关即将发布的 OpenAI 公告的传言时说道。

“There is a lot of uncertainty and unpleasantness that we already are experiencing.” Still, he noted, an AI-generated proof of the conjecture could open up new directions for researchers to pursue.

“我们已经经历了很多不确定性和不愉快。”不过，他指出，人工智能生成的猜想证明可以为研究人员的探索开辟新的方向。

If they can tease out the key assumptions in the proof — not always an easy task with AI-generated proofs — they might be able to learn a lot by tweaking those assumptions and exploring how the result changes.

如果他们能够梳理出证明中的关键假设（对于人工智能生成的证明来说这并不总是一件容易的任务），他们可能能够通过调整这些假设并探索结果如何变化来学到很多东西。

“It’s not ‘one and done,’” he said.

“这不是‘一劳永逸’，”他说。

Some researchers in math and theoretical computer science have responded to the rapid advances in AI capabilities by adopting AI tools for their own research.

一些数学和理论计算机科学领域的研究人员通过采用人工智能工具进行自己的研究来应对人工智能能力的快速进步。

Minzer, for his part, is concerned about how the new tools are changing the research process.

明泽则关心新工具如何改变研究过程。

The story of his new result is a case in point.

他的新结果的故事就是一个很好的例子。

“There is a lot of value in failing and knowing why you failed,” he said.

“失败并了解失败的原因非常有价值，”他说。

“Using AI takes all of this out.”

“使用人工智能可以解决这一切。”

He also worries about AI advances discouraging researchers from pursuing ambitious long-term projects.

他还担心人工智能的进步会阻碍研究人员追求雄心勃勃的长期项目。

“You are human, right?

“你是人类，对吧？

You need to sleep, you need to eat, you have moods,” he said.

你需要睡觉，你需要吃饭，你有情绪，”他说。

“You don’t know if you’re going to get scooped by the trillion-dollar company.”

“你不知道自己是否会被这家价值数万亿美元的公司抢先一步。”

Get highlights of the most important news delivered to your email inbox

获取发送到您的电子邮件收件箱的最重要新闻的摘要

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation.

《Quanta》杂志对评论进行审核，以促进知情、实质性、文明的对话。

Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected.

辱骂、亵渎、自我推销、误导、语无伦次或偏离主题的评论将被拒绝。

Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.

版主在正常工作时间（纽约时间）有工作人员，并且只能接受英文评论。