OpenAI称推翻ETH，Anthropic几小时后也交卷

OpenAI在前一天公布了三个长期困扰研究者的数学难题的解答。其中一项，是对 指数时间假设（ETH） 的意外否定——这个假设在计算机科学中根深蒂固，长期支撑着人们对"什么算难计算"的理解。 和前几次"证明投放"一样，科学界的反应是兴奋与不安交织。Anthropic的数学家Levent Alpöge提出，OpenAI的解答可能建立在已有工作之上；几小时后，Anthropic也发布了自己对ETH的否定。 不过OpenAI这次的处理方式在变化。针对涉及的三个学科，它给出了不同的发布结构：数学家拿到的是放在GitHub上的成果；计算机科学家组成了工作组，要求公开分享证明，并要求OpenAI出资办一场会议来讨论；物理学家组成的工作组则将决定他们的结果如何发布。 组织计算机领域回应的，是麻省理工学院教授Ryan Williams。他的研究正聚焦于这类计算复杂度问题，此前曾批评OpenAI的做法，把去年10月的那次证明投放称为"对数学家的DDOS攻击"。 但他同意与这些前沿实验室合作，帮助梳理对该领域至关重要的想法，他告诉TechCrunch。实验室请他协助解读这份解答，同行的还有加州大学圣迭戈分校的计算机科学家Russell Impagliazzo和Ramamohan Paturi——两人在1999年首次发表了ETH。 他们的第一步是发布一封公开信，呼吁对这些问题感兴趣的科学家提供反馈，并讨论AI对该领域贡献的规范。 "（OpenAI的证明）有些部分，也许你可以说是常规的，但确实有两三个看起来像外星来的部分，正是这些部分让我觉得，哇，这是整个社区需要一起攻克的东西，"Williams对TechCrunch说。 P与NP的老问题 ETH属于一类更广泛的问题，即P与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都是低垂的果实，我该如何提高我想提出的科学问题的门槛？" 特别