OpenAI称AI驳斥了指数时间假说，MIT教授：这不是最终答案

Image Credits: ChatGPT

OpenAI又往学界扔了三颗炸弹。这次是三个长期悬而未决的数学难题，其中一颗直接炸到了计算机科学的地基上：指数时间假说（ETH）。

科学界既兴奋又不安。Anthropic数学家Levent Alpöge在X上暗示，OpenAI的解法基于已有的工作。几小时后，Anthropic也发布了自己的ETH反驳。

OpenAI的流程变了。三个学科，三种待遇：数学家那边，直接扔GitHub；计算机科学家这边，组成工作组，要求公开分享证明，OpenAI还得掏钱资助会议；物理学家那边，成立工作组决定发布方式。看起来OpenAI在学着和各学科打交道。

MIT教授Ryan Williams负责组织计算机科学界的回应。这人之前骂过OpenAI，说他们的做法是“对数学家的DDOS攻击”。这次他同意合作，因为这些想法对领域太重要了。OpenAI请Williams，以及1999年提出ETH的Russell Impagliazzo和Ramamohan Paturi，一起解读。他们先发了一封公开信征求反馈。

Williams说，OpenAI的证明里大部分内容“可以说是常规的”，但有两三个看起来“像外星产物”的部分。正是这些部分让他意识到，整个学界需要一起攻克。

要理解这事，得回到P和NP。

NP问题，验证容易，求解难。数独是典型的例子：填好的九宫格检查起来很快，但自己填，可能耗上一辈子。P=NP的意思是，所有验证快的问题，求解也快。这好得不像真的。所以大多数科学家相信P≠NP。

ETH给P≠NP提供了证据支撑。它说的是：对一类特定的逻辑难题，哪怕用最快的算法，变量一多，求解时间也得指数级增长。

OpenAI和Anthropic声称，他们的模型提出了“亚指数时间”算法，比指数级快。如果成立，ETH就被推翻了。更进一步的联想是，P=NP也许没那么遥远。

Williams说，每个计算机科学家都应该给P=NP的可能性多一点点权重，但具体多少，每个人自己衡量。他承认这个发现动摇了很多关于“哪些问题算难”的直觉。但他不觉得这是最终答案：“OpenAI的算法不可能是你能得到的最好的算法。”

影响是实打实的。过去十年，大量论文把ETH当背景假设。如果ETH倒了，这些研究得重看。Williams推动OpenAI资助一个会议，就是要弄清楚“接下来怎么办”。

在谈学术影响之前，得先回答安全问题。更快的算法可能意味着，某些密钥长度的密码系统不再安全。Williams问OpenAI科学负责人Dan Roberts的第一件事就是：“检查过对现有密码系统的影响了？有没有什么现在就不安全了？”Roberts说查了，没有发现能造成实际破坏的漏洞。

AI参与科学发现的模式还在磨合期。Williams说，AI在“逼着人们把工作做得更有野心”，如果以前研究的东西对AI来说都是低垂的果实，那科学家得想想怎么把标准抬高。

以前，AI帮人找答案。现在，AI在逼人换问题。