前沿 AI 实验室称其模型推翻了“指数时间假说”，这意味着什么？
英文标题：Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
OpenAI 与 Anthropic 相继发布成果，声称其 AI 模型提出了能在亚指数时间内解决特定逻辑难题的算法，从而推翻了计算机科学中长期存在的“指数时间假说（ETH）”。MIT 计算机科学家 Ryan Williams 正携手 ETH 提出者组织学界进行同行评审，并指出 OpenAI 证明中包含若干“异星般奇特”的全新推导部分。如果该结论成立，将从根本上撼动学术界对计算复杂性及“P ≠ NP”问题的直觉认知，虽初步评估未危及现有密码学体系，但正深刻重塑理论计算机科学的研究基石与范式。
3.1 KB
389 B
294.3 KB
6.7 KB
53.0 KB
248 B
394.6 KB
中文
OpenAI 发布了针对长期困扰研究界的三个重大数学难题的解答。其中一项是对“指数时间假说”（Exponential Time Hypothesis, ETH）的意外推翻——ETH 是计算机科学中一项长期存在的基石假设，在我们理解“哪些问题难以计算”方面起着至关重要的作用。
与该前沿实验室以往突击发布数学证明的做法类似，科学界的反应交织着兴奋与忧虑。Anthropic 数学家 Levent Alpöge 指出 OpenAI 的成果可能借鉴了已有工作，数小时后，Anthropic 随后也发布了自己对 ETH 的反驳成果。
不过，OpenAI 的成果发布方式正在演进。这一次，该实验室针对涉及的三个学科采用了不同的发布方式：数学家直接在 GitHub 上获取了成果；计算机科学家组成了工作组，要求公开发布证明，并希望 OpenAI 资助一场研讨会以展开深入讨论；物理学家则组成了工作组，由其决定后续如何发布其成果。
麻省理工学院（MIT）教授 Ryan Williams 正是组织计算机科学领域研判这项新发现的核心学者。Williams 的研究重点正是这些计算复杂性问题，他此前曾批评过 OpenAI 的做法，在今年 10 月初将 OpenAI 突然倾倒证明的行为称为对数学家的“DDOS 攻击”。
然而，他告诉 TechCrunch，自己同意与这些前沿实验室合作，以协助梳理对该领域至关重要的学术思想。OpenAI 邀请他协助解读该解答，一同受邀的还有加州大学圣迭戈分校（UC San Diego）计算机科学家 Russell Impagliazzo 和 Ramamohan Paturi，他们曾在 1999 年首次提出了 ETH。
他们的第一步是发表一封公开信，呼吁关注这些问题的科学家提供反馈，并就 AI 介入科学工作的规范展开讨论。
“（OpenAI 证明的）某些部分或许可以说是常规手段，但确实存在两到三处看起来非常‘异星化’（alien-looking）的部分，也正是看到这几处后让我意识到，天哪，这是整个学术界需要共同攻克的东西，”Williams 告诉 TechCrunch。
你理解 P 与 NP 问题吗？
ETH 属于更广泛的“P 对 NP”（P versus NP）问题大类，该问题数十年来一直推动着计算机科学及许多其他领域的发展。简而言之，研究人员试图探究：是否任何解答易于验证（NP）的问题，也能被轻易求解（P）。
一个简单的例子是数独游戏：一旦填好解法，很容易快速验证其对错，但寻找解法的过程却非常耗时。这种机制广泛存在于众多关键问题中，也是现代密码学体系的基石所在：当你拥有密文的密钥时，可以立刻解密；但如果要直接破解有效密码，所需时间过长，以至于在实际中根本不可行。
然而，科学家们至今仍未能证明这一规律是否总是成立。“P = NP 意味着，你不仅能在数独解答存在时快速验证它，还能直接生成它，”Williams 表示，“P = NP 断言这对每一个可以快速验证的问题都成立——只要你能快速验证它，你就能快速解决它。所以这听起来未免好得不真实。”
正因如此，绝大多数科学家都倾向于假设 P ≠ NP，而 ETH 则为这一假设提供了理论支撑。它基本上表明：对于某类棘手的逻辑谜题，随着变量数量的增加，哪怕是最快的计算机算法寻找解所需的时间也会呈指数级激增。
OpenAI 和 Anthropic 的主张在于，其模型找到了能在“亚指数”（sub-exponential）时间内解决这些谜题的算法，这意味着其运算速度超越了以往认为的理论极限。如果属实，它们可能已经证明了 ETH 是错误的——用学术术语来说就是推翻了它——并可能为通往 P = NP 的通用算法开辟了一条路径。
“每位计算机科学家或许都应该对 P = NP 的成立可能性多赋予一点权重，但每个人的看法各不相同，”Williams 说，“我认为这确实在某种程度上挑战了我们此前对……困难 NP 问题可解性（tractability）抱有的大量直觉认知。同时我也认为，这大概率还不是终极答案。我不觉得 OpenAI 的算法会是理论上能达到的最优算法。”
计算机科学家面临的后续任务
Williams 指出，由于 ETH 的长期坚挺，过去十年中有大量学术论文都将其作为前提假设；如果 AI 实验室推翻该假说的结论成立，这些论文都将面临重新审视。
“这也是为什么我此前要求并推动 OpenAI 为此赞助一场学术研讨会的部分原因——它将波及许多研究人员的工作，我们需要弄清楚，除了理解算法本身，接下来还会发生什么。我们需要搞清楚，与我们以往掌握的认知相比，整个基础理论该如何调整？”他说道。
在学术理论考量之外，还有网络安全层面的疑问。Williams 表示，更优的算法可能意味着依赖特定密钥长度的密码系统将不再安全。因此，他向 OpenAI 科学负责人 Dan Roberts 提出的首批问题之一便是“他们是否核查过这是否会对任何密码系统产生冲击……现在是否有任何系统变得不安全？显然他们进行了检查，并且相当有把握这……并不意味着破解了现有加密。”
这种基于 AI 的科学发现新范式仍处于探索阶段，但 Williams 表示，尽管存在切实担忧——尤其是关乎下一代科学家的培养，但他依然保持乐观。作为一位涉足高深数学研究的计算机科学家，相较于纯数学家，他适应这种转变可能相对容易一些。
不过他表示，AI 正在“迫使人们对自己的研究工作抱有更大的雄心，并促使大家更深入地思考：如果我过去研究的内容现在都成了 AI 触手可及的低垂果实，那么我该如何提高门槛，去探索更高维度的科学问题？”
English / 原文
OpenAI released solutions to three blockbuster math problems that have long vexed researchers. One was a surprise rejection of the Exponential Time Hypothesis (ETH), a durable assumption in computer science that plays a large role in how we understand what is difficult to compute.
As with previous proof-drops from the frontier lab, scientific communities responded with a mixture of thrill and dismay. Anthropic mathematician Levent Alpöge suggested that OpenAI was basing its solutions on pre-existing work, and hours later, Anthropic subsequently released its own refutation of ETH.
However, OpenAI’s process is evolving. This time, the lab structured its releases differently for each of the three disciplines involved: Mathematicians got the work dropped on GitHub; the computer scientists formed a working group, asked for the proofs to be shared publicly and OpenAI to fund a conference to discuss them; the physicists formed a working group that will determine how their result will be released.
MIT professor Ryan Williams is the computer scientist who is organizing his field’s response to the new finding. Williams, whose work focuses on these questions of computational complexity, has criticized OpenAI’s approach in the past, calling its proof dump earlier this October a “DDOS attack on mathematicians.”
However, he agreed to collaborate with the frontier labs in order to help shepherd ideas that are vital to the field, he told TechCrunch. The lab asked him to help interpret the solution, along with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the ETH in 1999.
Their first step was to release an open letter calling for feedback from scientists interested in these problems and a discussion of the norms around AI contributions to their work.
“Some parts [of OpenAI’s proof] are, maybe you could say routine, but then yes, there are two or three alien-looking parts, and it’s exactly these parts that I saw that made me think, wow, this is something that the whole community needs to work on together,” Williams told TechCrunch.
Are you down with P versus NP?
The ETH is part of a broader class of problems known as P versus NP, which has animated computer science and many other fields for decades. Reductively, researchers are trying to understand if any problem whose solution can be easily verified (NP) can also be easily solved (P).
A simple example is the game Sodoku: Once a solution to a puzzle is in place, it can be quickly verified, but finding the solution is time-consuming. That dynamic is true across a range of important problems, and the insight underpins cryptographic systems: When you have the key to an encoded message, you can reveal it, but actually cracking an effective code takes too long to be useful.
However, scientists have yet to prove whether that is always true. “P = NP is saying that, not only can you verify Sudoku solutions when they exist, you can just generate them,” Williams said. “P = NP is asserting that this is true for every single problem you can verify quickly — if you can verify it quickly, you can solve it quickly. So this just seems too good to be true.”
That’s why most scientists assume that P ≠ NP. ETH provided evidence for that. It basically says that even the fastest computer algorithm needs exponentially more time to find a solution as the number of variables grow in a specific class of tricky logic puzzle.
The claims from OpenAI and Anthropic is that their models have come up with algorithms that solve those puzzles in “sub-exponential” time, meaning faster than the speeds previously thought possible. If true, they may have proven the EFT to be false — refuted it, in scientific terms — and maybe opened up a path for algorithms that generally perform P = NP.
“Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one’s weight may vary,” Williams said. “I do think that it kind of calls into question a lot of the intuitions that we thought we had about … how tractable [hard NP problems] are. I also think that this is probably not the final answer either. I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get.”
The work ahead for computer scientists
The durability of ETH has lead to it being included in many scientific papers over the past decade that will need to be revisited if the AI labs claims that they’ve proven it wrong holds up, Williams said.
“This is partly why I was asking or pushing OpenAI to support a conference on this — it’s going to affect many researchers’ works, and we need to figure out, okay, what happens next besides understanding the algorithms. We need to understand, how should the foundations change compared to what we had before?” he said.
Before scientific concerns, there are cybersecurity questions. Williams said that an improved algorithm could imply that cryptographic systems relying on certain key sizes could be considered broken. So one of the first questions he asked OpenAI science lead Dan Roberts “was if they had checked that this affects any crypto systems … is anything insecure now? And apparently, they checked, and they were reasonably confident that this didn’t … imply any breaks.”
This new AI paradigm of scientific discovery is still a work in progress, but Williams says he is optimistic despite real concerns, particularly about training the next generation of scientists. Being a computer scientist who does high level math has perhaps made the adjustment easier for him than for pure mathematicians.
Still, he says AI is “forcing people to be a little more ambitious about the kind of work that they do, and to think more deeply about, okay, if all the things I used to work on are now low-hanging fruit for AI, how can I raise the bar for the kind of scientific questions I want to ask?”