前沿 AI 实验室称模型推翻 ETH，计算机科学界如何回应
Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
OpenAI 公布了对三个数学难题的解答，其中一项是对计算机科学长期假设指数时间假说（ETH）的否定，Anthropic 随后也发布了自己的 ETH 反驳。MIT 教授 Ryan Williams 与 UC San Diego 的 Russell Impagliazzo、Ramamohan Paturi 受 OpenAI 邀请协助解读，并发布公开信征集反馈、讨论 AI 贡献的规范。Williams 表示，若该结论成立，过去十年大量依赖 ETH 的论文需要重新审视，他还曾向 OpenAI 科学负责人 Dan Roberts 确认是否影响现有密码系统，对方称已检查且认为不会导致破解。
正文 · AI 翻译
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 对其工作贡献的规范。
Williams 告诉 TechCrunch：“（OpenAI 证明的）有些部分，也许你可以说是常规的，但没错，有两三个看起来像外星人般的部分，而正是我看到的这些部分让我想到，哇，这是整个社区需要共同研究的事情。”
你接受 P 与 NP 吗？
ETH 属于一类更广泛的问题，即 P 与 NP 问题，几十年来一直激发着计算机科学和许多其他领域的讨论。简而言之，研究人员试图理解，是否任何解可以被轻易验证的问题（NP）也能被轻易求解（P）。
一个简单的例子是数独游戏：一旦谜题有了答案，就可以快速验证，但找到答案却很耗时。这种动态在一系列重要问题中都成立，而这一洞见支撑着密码系统：当你拥有编码信息的密钥时，你可以揭示它，但真正破解一个有效密码所需时间太长，因而没有实用价值。
然而，科学家尚未证明这是否总是成立。Williams 说：“P = NP 是说，你不仅能在数独解存在时验证它们，你还能直接生成它们。P = NP 断言这对每一个你能快速验证的问题都成立——如果你能快速验证它，你就能快速求解它。所以这看起来好得令人难以置信。”
这就是为什么大多数科学家假设 P ≠ NP。ETH 为此提供了证据。它基本上是说，对于某一类棘手的逻辑谜题，随着变量数量的增长，即使最快的计算机算法也需要指数级更多的时间来找到解。
OpenAI 和 Anthropic 声称，它们的模型提出了能在“次指数”时间内解决这些谜题的算法，这意味着比此前认为可能的速度更快。如果属实，它们可能已经证明 ETH 为假——用科学术语说，就是反驳了它——并且也许为通常实现 P = NP 的算法开辟了道路。
Williams 说：“每位计算机科学家或许都应该对 P = NP 的可能性多给一点权重，但权重可能因人而异。我确实认为，这在一定程度上让我们此前关于……（困难的 NP 问题）有多易处理的许多直觉受到质疑。我也认为这大概也不是最终答案。我不认为 OpenAI 的算法可能是你能得到的最佳算法。”
计算机科学家面前的工作
Williams 说，ETH 的持久性导致它在过去十年被纳入许多科学论文，如果 AI 实验室关于已证明其错误的说法成立，这些论文将需要重新审视。
他说：“这也是我为什么请求或推动 OpenAI 支持一场关于此事的会议的部分原因——它将影响许多研究人员的工作，我们需要弄清楚，好吧，除了理解这些算法之外，接下来会发生什么？我们需要理解，与以前相比，基础应该如何改变？”在科学关切之前，还有网络安全问题。Williams 说，改进的算法可能意味着依赖某些密钥长度的密码系统可被视为已被破解。因此，他向 OpenAI 科学负责人 Dan Roberts 提出的首批问题之一“就是他们是否检查过这会影响任何密码系统……现在是否有任何东西不安全？显然，他们检查过，并且相当有信心这……不意味着任何破解。”
这种科学发现的新 AI 范式仍在发展中，但 Williams 表示，尽管存在真实担忧，他仍持乐观态度，尤其是关于培养下一代科学家。作为一名从事高水平数学的计算机科学家，这或许使他比纯数学家更容易适应。
不过，他说 AI 正“迫使人们对自己所做的工作更有雄心，并更深入地思考，好吧，如果我过去从事的所有事情现在对 AI 来说都是唾手可得的成果，我该如何提高我想提出的科学问题的标准？”