OpenAI 称模型推翻 ETH 假设，Anthropic 数小时后发布反驳

OpenAI 昨天发布了三个长期困扰研究者的重磅数学问题的解决方案。其中之一出人意料地否定了指数时间假说（ETH），这是计算机科学中一个长期稳固的假设，在我们理解什么难以计算方面扮演着重要角色。

与这家前沿实验室此前发布证明时一样，科学界的反应是兴奋与沮丧交织。Anthropic 数学家 Levent Alpöge暗示OpenAI 的解决方案是基于已有的工作，数小时后，Anthropic 随后发布了自己对 ETH 的反驳。

然而，OpenAI 的流程正在演变。这一次，该实验室以不同的方式组织发布针对所涉及的三个学科分别采用了不同做法：数学家的工作被放到 GitHub 上；计算机科学家成立了一个工作组，要求公开分享证明，并要求 OpenAI 资助一场会议来讨论这些证明；物理学家成立了一个工作组，将决定他们的结果如何发布。

麻省理工学院教授 Ryan Williams 是组织其所在领域对这项新发现作出回应的计算机科学家。Williams 的研究聚焦于这些计算复杂度问题，他过去曾批评过 OpenAI 的做法，称其今年 10 月早些时候发布的证明是“对数学家的 DDOS 攻击”。

不过，他告诉 TechCrunch，他同意与这些前沿实验室合作，以帮助引导对该领域至关重要的想法。该实验室请他帮助解读这一解决方案，同时参与的还有加州大学圣地亚哥分校的计算机科学家 Russell Impagliazzo 和 Ramamohan Paturi，后者于 1999 年首次发表了 ETH。

他们的第一步是发布一封公开信呼吁对这些问题的科学家提供反馈，并讨论 AI 对其工作贡献的相关规范。

“（OpenAI 证明的）某些部分，也许你可以说是常规的，但没错，有两三个看起来像外星人般的部分，而正是我看到的这些部分让我想到，哇，这是整个社区需要共同研究的东西，”Williams 告诉 TechCrunch。

你支持 P vs NP 吗？

ETH 属于一类更广泛的问题，即 P vs NP，这个问题几十年来一直激发着计算机科学和许多其他领域的兴趣。简而言之，研究人员试图弄清楚，是否所有解能够被快速验证的问题（NP）也能够被快速求解（P）。

一个简单的例子是数独游戏：一旦谜题的解已经就位，它就能被快速验证，但找到解却很耗时。这种动态在一系列重要问题中都成立，而这一洞见支撑着密码系统：当你拥有编码消息的密钥时，你可以将其揭示出来，但真正破解一个有效的密码所需时间太长，以至于没有实用价值。

然而，科学家们尚未证明这是否总是成立。“P = NP 说的是，你不仅能在数独解存在时验证它们，你还能直接生成它们，”Williams 说。“P = NP 断言的是，这对每一个你能快速验证的问题都成立——如果你能快速验证它，你就能快速求解它。所以这看起来简直好得不像真的。”

这就是为什么大多数科学家假设 P ≠ NP。ETH 为此提供了证据。它基本上是说，对于某一类棘手的逻辑谜题，随着变量数量的增长，即使是最快的计算机算法也需要指数级更多的时间来找到解。

OpenAI 和 Anthropic 声称，它们的模型已经提出了能在“次指数”时间内解决这些谜题的算法，这意味着比之前认为可能的速度更快。如果属实，它们可能已经证明了 EFT 为假——用科学术语说，就是反驳了它——并且也许为通常能实现 P = NP 的算法开辟了一条道路。

“每一位计算机科学家大概都应该对 P = NP 的可能性多给一点权重，但每个人的权重可能不同，”Williams 说。“我确实认为，这在一定程度上让我们对我们自以为拥有的许多直觉产生了怀疑……关于[困难的 NP 问题]有多易处理。我也认为这大概也不是最终答案。我不认为 OpenAI 的算法可能是你能得到的最佳算法。”

计算机科学家面前的工作

Williams 表示，ETH 的持久性使其在过去十年间被纳入许多科学论文，如果 AI 实验室声称已证明其错误的说法成立，这些论文将需要重新审视。

这种科学发现的新 AI 范式仍在推进中，但 Williams 表示，尽管存在切实的担忧，他仍持乐观态度，尤其是关于培养下一代科学家方面。作为一名从事高水平数学工作的计算机科学家，这或许让他比纯数学家更容易适应。

尽管如此，他表示 AI 正在“迫使人们对自己所做的工作更有雄心，并更深入地思考，好吧，如果我过去做的所有事情现在对 AI 来说都是唾手可得的成果，我该如何提高我想提出的科学问题的标准？”