OpenAI 发布数学证明 挑战指数时间假设

OpenAI 昨日发布了针对三个长期困扰研究人员的重磅数学问题的解决方案。其中一项成果出人意料地否定了指数时间假设（Exponential Time Hypothesis, ETH），这是计算机科学中一个经久不衰的假设，在我们理解计算难度方面发挥着重要作用。

与这家前沿实验室此前发布的证明类似，科学界对此反应不一，既感到兴奋又充满忧虑。Anthropic 数学家 Levent Alpöge 指出，OpenAI 的解决方案似乎基于已有的研究成果；几小时后，Anthropic 随后也发布了其自身对 ETH 的反驳。

然而，OpenAI 的流程正在演变。这一次，该实验室为涉及的三个学科分别采取了不同的发布策略：数学家们直接在 GitHub 上获取了相关成果；计算机科学家组成了一个工作组，要求公开分享证明，并希望 OpenAI 资助一场会议以讨论这些内容；物理学家则成立了一个工作组，将决定其成果的发布方式。

麻省理工学院教授 Ryan Williams 是负责协调其所在领域对新发现回应工作的计算机科学家。Williams 的研究重点正是计算复杂性相关问题，他过去曾批评 OpenAI 的做法，称其在今年十月早些时候进行的“证明倾倒”行为是对数学家的“DDOS 攻击”。

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

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

Williams 告诉 TechCrunch：“[OpenAI 的证明]有些部分或许可以说是常规的，但确实有两到三个看起来非常陌生的部分，正是这些部分让我意识到，哇，这是整个社区需要共同攻克的问题。”

var playerInstance_jwplayer_6ae0da82df6f5 = jwplayer( "jwplayer_6ae0da82df6f5" ); playerInstance_jwplayer_6ae0da82df6f5.setup({ playlist: "https://cdn.jwplayer.com/v2/media/GtfnxAFg", });

你了解 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 的算法可能是你能得到的最佳算法。”

计算机科学家未来的工作

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

“这也是我为什么一直在询问或推动 OpenAI 支持举办相关会议的部分原因——这将影响许多研究人员的工作，我们需要弄清楚，除了理解算法之外，接下来会发生什么？我们需要理解，我们之前所依赖的基础应该是什么？”他说。

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

这种用于科学发现的新 AI 范式仍处于发展阶段，但 Williams 表示，尽管存在真实的担忧，尤其是关于培养下一代科学家的问题，他仍持乐观态度。作为一名从事高等数学研究的计算机科学家，这种转变对他来说或许比纯数学家更容易适应。

不过，他表示 AI 正在“迫使人们对自己所做的工作类型更加雄心勃勃，并更深入地思考：好吧，如果我过去研究的所有内容现在对 AI 来说都是唾手可得的成果，我该如何提高我想要提出的科学问题的标准？”