前沿 AI 实验室称其模型推翻了指数时间假设。这意味着什么？

OpenAI 昨天发布了三个长期困扰研究人员的重磅数学问题的解决方案。其中一个是出人意料地驳回了指数时间假设 (ETH)，这是计算机科学中一个持久的假设，在我们理解什么是难以计算的问题方面起着重要作用。

正如这家前沿实验室此前发布的证明一样，科学界对此的反应喜忧参半。Anthropic 数学家 Levent Alpöge 暗示 OpenAI 的解决方案是基于现有工作的，几个小时后，Anthropic 随后 发布 了自己对 ETH 的驳斥。

然而，OpenAI 的流程正在进化。这一次，实验室针对涉及的三个学科分别 采用了不同的发布结构：数学家在 GitHub 上获得了这些工作；计算机科学家成立了一个工作组，要求公开分享这些证明，并要求 OpenAI 资助一个会议来讨论它们；物理学家成立了一个工作组，将决定如何发布他们的结果。

MIT 教授 Ryan Williams 是一位计算机科学家，他正在组织其领域对这一新发现的反应。Williams 的工作专注于这些计算复杂度问题，他过去曾批评过 OpenAI 的做法，称 其今年 10 月早些时候发布的证明是“对数学家的 DDOS 攻击”。

然而，他告诉 TechCrunch，他同意与这些前沿实验室合作，以帮助引导对该领域至关重要的想法。实验室邀请他协助解释该解决方案，一同参与的还有 UC San Diego 计算机科学家 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 为此提供了证据。它基本上是说，随着一类特定棘手逻辑难题中变量数量的增加，即使是最快的计算机算法也需要呈指数级增长的时间来寻找解决方案。