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

OpenAI 昨天发布了三个长期困扰研究人员的重磅数学问题的解决方案。其中之一是对指数时间假设（ETH）的出人意料的否定，这是一个在计算机科学中持久存在的假设，对我们理解计算难度起着重要作用。

正如该前沿实验室以往的证明发布一样，科学界对此反应复杂，既兴奋又沮丧。Anthropic 的数学家 Levent Alpöge 指出 OpenAI 的解决方案基于现有研究，几小时后，Anthropic 随后也 发布了其对 ETH 的反驳。

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

麻省理工学院教授瑞安·威廉姆斯（Ryan Williams）是一位计算机科学家，他正在组织其领域对这一新发现的反应。威廉姆斯的长期研究聚焦于这些计算复杂性问题，他过去曾批评 OpenAI 的做法，称其在今年 10 月初发布的证明堆砌是对数学家的“DDoS 攻击”。

不过，他在接受 TechCrunch 采访时表示，他同意与前沿实验室合作，以帮助引导对该领域至关重要的思想。实验室邀请他协助解读该解决方案，并邀请了加州大学圣迭戈分校的计算机科学家拉塞尔·伊姆帕利亚佐（Russell Impagliazzo）和拉马莫汉·帕图里（Ramamohan Paturi），他们于 1999 年首次发表了 ETH。

他们的第一步是发布一封公开信，呼吁对这些问题感兴趣的科学家提供反馈，并讨论围绕人工智能对其工作贡献的行为规范。

“（OpenAI 证明的）某些部分，你也许可以说它是常规的，但确实有两到三个看起来很诡异的部分，正是这些部分让我觉得，哇，这是整个社区需要共同努力的事情，”威廉姆斯告诉 TechCrunch。

你了解 P对NP 问题吗？

ETH 是被称为 P对NP（P vs NP）的更广泛问题类别的一部分，几十年来，这一问题一直活跃于计算机科学和许多其他领域。简单来说，研究人员正试图弄清楚，任何其解决方案可以被轻易验证的问题（NP）是否也能被轻易解决（P）。

一个简单的例子是数独游戏：一旦填好了解法，它就能被快速验证，但要找到这个解法却很耗时。这种动态关系适用于一系列重要问题，这一见解也是密码系统的基础：当你拥有加密信息的密钥时，你可以将其解密，但实际上破解一个有效的密码所需的时间太长，以至于无法派上用场。

然而，科学家们尚未证明这是否总是真的。“P = NP 的意思是，不仅在你拥有数独解法时可以验证它们，你还可以直接生成它们，”威廉姆斯说。“P = NP 断言，这对于你能快速验证的每一个问题都是成立的——如果你能快速验证它，你就能快速解决它。所以这听起来似乎有点好得难以置信。”

这就是为什么大多数科学家认为 P ≠ NP。ETH 为此提供了证据。它基本上说明了，在某一特定类别的棘手逻辑谜题中，随着变量数量的增长，即使是最快的计算机算法也需要呈指数级增长的时间来寻找解决方案。

OpenAI 和 Anthropic 声称，他们的模型已经设计出了能够在“亚指数”时间内解决这些谜题的算法，这意味着其速度比以往认为的极限更快。如果属实，他们可能已经证明了 EFT 是错误的——用科学术语来说就是反驳了它——并可能为通常表现为 P = NP 的算法铺平了道路。

“每个计算机科学家或许都应该对 P = NP 的合理性给予更多的权重，尽管每个人的看法可能有所不同，”Williams 说。“我确实认为，这在某种程度上让我们对……[困难的 NP 问题] 的易解性所拥有的许多直觉产生了怀疑。我也认为这大概还不是最终的答案。我不认为 OpenAI 的算法会是你所能得到的最好算法。”

计算机科学家面前的工作

Williams 表示，ETH 的稳固性使其在过去十年中被纳入了许多科学论文中，如果人工智能实验室声称已证明其错误的说法站得住脚，这些论文将需要重新审视。

“这部分原因也是我要求或推动 OpenAI 支持召开相关会议的原因——它将影响许多研究人员的工作，我们需要弄清楚，好吧，除了理解算法之外，接下来会发生什么，我们需要明白，我们以前的基础应该是什么？”他说。

在科学问题之前，还有网络安全问题。Williams 表示，改进后的算法可能意味着依赖特定密钥大小的加密系统将被视为遭到破解。因此，他向 OpenAI 科学负责人 Dan Roberts 提出的首要问题之一“是他们是否检查过这是否会影响任何加密系统……现在有什么是不安全的吗？显然，他们检查过了，并且有相当大的信心认为这……并不意味着任何破解。”

这种科学发现的新人工智能范式仍在进行中，但 Williams 表示，尽管存在真正的担忧，特别是关于培养下一代科学家的问题，他依然保持乐观。作为一个从事高级数学研究的计算机科学家，相比纯数学家，他或许更容易适应这种转变。

不过，他表示，人工智能正在“迫使人们对他们所做的工作抱有更大的雄心，并更深入地思考：如果我过去研究的所有东西现在对人工智能来说都是触手可及的果实，我该如何提高我想问的科学问题的门槛？”

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