OpenAI 与 Anthropic 模型声称反驳指数时间假说，计算机科学家解读影响

OpenAI 昨天发布了针对三个长期困扰研究人员的重磅数学问题的解答。其中一项出人意料地否定了指数时间假说（ETH）——计算机科学中一个根深蒂固的假设，在我们理解哪些问题难以计算方面扮演着重要角色。

与这家前沿实验室此前发布证明时一样，科学界界的反应掺杂着兴奋与不安。Anthropic 数学家 Levent Alpöge 提出，OpenAI 的解答是基于已有工作得出的，几个小时后，Anthropic 随后也发布了自己对 ETH 的反驳。

不过，OpenAI 的发布流程正在演进。这一次，该实验室针对涉及的三个学科采取了不同的发布方式：数学家收到的是直接发布在 GitHub 上的成果；计算机科学家组成了一个工作组，要求公开分享证明，并希望 OpenAI 资助一场讨论这些证明的会议；物理学家则组成了一个工作组，由其决定他们的成果如何发布。

MIT 教授 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 声称，他们的模型已经想出了能在“亚指数级”时间内解开这些谜题的算法，也就是比此前认为可能的速度更快。如果属实，他们可能已经证明 ETH 是错误的——用科学术语说就是被驳倒了——并或许为普遍实现 P = NP 的算法开辟了一条道路。

“每位计算机科学家或许都应该对 P = NP 的可能性多加一点砝码，但每个人的砝码可以不同，”Williams 说。“我确实认为，这在某种程度上让我们质疑了此前对……这些难解的 NP 问题有多‘可解’的许多直觉。我也认为，这大概不是最终答案。我不认为 OpenAI 的算法可能是你能得到的最好算法。”

计算机科学家们面前的工作

Williams 说，由于 ETH 长期稳固的地位，过去十年许多科学论文都采用了它；如果这些 AI 实验室声称已将其证伪的说法站得住脚，那么这些论文都需要重新审视。

“这也是我部分上为什么要请求或推动 OpenAI 支持一场关于此事的会议——它将影响许多研究者的工作，我们需要搞清楚，好吧，在理解这些算法之外，接下来会怎样，我们还需要理解，我们此前应该以什么样的基础为准？”他说。

在科学层面的担忧之前，还有网络安全的问题。Williams 说，一种更好的算法可能意味着，依赖某些密钥长度的密码系统将被视为已被破解。因此他问 OpenAI 科学负责人 Dan Roberts 的第一个问题“就是他们是否检查过这是否会影响任何密码系统……现在是否有什么东西不再安全了？显然，他们检查过了，而且相当有把握认为这并……不意味着任何破解。”

这种由 AI 驱动的科学发现新范式仍在推进之中，但尽管存在一些现实的担忧——尤其是关于培养下一代科学家的问题——Williams 表示他是乐观的。作为一名从事高等数学工作的计算机科学家，这种转变对他来说或许比纯粹的数学家更容易适应。

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

当您通过我们文章中的链接购买时，我们可能会获得少量佣金。这不会影响我们的编辑独立性。