OpenAI发布了针对三个长期困扰研究者的重大数学难题的解决方案。其中一个令人意外的是对指数时间假设(ETH)的否定。ETH是计算机科学中的一个重要假设,影响着我们对计算难度的理解。
与此前前沿实验室发布的证明一样,科学界对此反应复杂,既有兴奋也有担忧。Anthropic的数学家Levent Alpöge曾暗示OpenAI的解决方案基于已有成果,随后Anthropic也发布了自己对ETH的反驳。
不过,OpenAI这次的发布方式有所不同。针对涉及的三个学科,OpenAI采取了不同的策略:数学家们在GitHub上获得了相关工作;计算机科学家组建了工作组,要求公开证明并由OpenAI资助召开讨论会议;物理学家则成立工作组决定如何发布他们的结果。
麻省理工学院教授、计算复杂性领域专家Ryan Williams负责组织计算机科学界对这一新发现的回应。Williams此前批评过OpenAI的做法,称其早前的证明发布是对数学家的“拒绝服务攻击”。
但他同意与前沿实验室合作,帮助解读这些对领域至关重要的想法。OpenAI邀请他与加州大学圣地亚哥分校的计算机科学家Russell Impagliazzo和Ramamohan Paturi(ETH的首次提出者)共同参与。
他们的第一步是发布公开信,邀请科学家们反馈意见,并讨论AI对他们工作的贡献规范。
Williams表示:“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的算法是最优的。”
计算机科学家的后续工作
ETH的持久性使其成为过去十年许多论文的基础,如果AI实验室的推翻成立,这些研究都需重新审视。
Williams表示:“这也是我推动OpenAI支持召开相关会议的原因——这将影响许多研究者的工作,我们需要弄清楚,除了理解算法之外,基础理论应如何调整。”
在科学问题之外,还有网络安全的考量。Williams提到,改进的算法可能意味着依赖特定密钥长度的密码系统不再安全。他曾询问OpenAI科学负责人Dan Roberts是否检查过对密码系统的影响,得到的答复是他们进行了检查,并有信心目前没有安全漏洞。
这种由AI驱动的科学发现新范式仍在发展中,但Williams对未来持乐观态度,尽管存在一些担忧,尤其是对下一代科学家的培养。作为一名同时具备计算机科学和高等数学背景的研究者,他认为自己比纯数学家更容易适应这种变化。
他还说,AI“促使人们对自己所做的工作更有雄心,深入思考:如果以前的研究成果对AI来说都是轻而易举的,那么我如何提高自己提出科学问题的水平?”


