OpenAI称其人工智能模型找到了证伪指数时间假说（ETH）的方法，这是1999年提出的一项计算机科学猜想。该声明与以ETH为交易代码的加密货币以太坊（Ethereum）及其联合创始人Vitalik Buterin均无任何关联。

尽管如此，这一消息还是在Crypto Twitter上引发了不少玩笑。用户Takumi在X上发帖称：“该死的量化交易员把$ETH杀得片甲不留”，Andrew Jiang则调侃道：“自从这消息出来后，Vitalik一直很安静。”

此次涉及的ETH由计算机科学家Russell Impagliazzo、Ramamohan Paturi和Francis Zane提出。该假说认为，名为3-SAT的逻辑问题无法比逐一检验所有变量组合快得多地求解。在3-SAT中，目标是判断真或假的赋值能否满足一组规则，每条规则包含三个变量。

据OpenAI介绍，数百篇学术论文依赖该假说来证明图论、计算生物学、数据库和几何学中的某些问题无法快速求解。OpenAI表示，证伪ETH可能重新引发关于这些问题能被加快多少的讨论，并帮助研究者寻找更好的算法。

“对ETH的反驳重新打开了这些问题还能提速多少的讨论，”OpenAI在其博客文章中写道，“并可能有助于指导更优算法的搜寻。”

OpenAI这篇67页的论文日期为10月17日、10月25日修订，描述了一种确定性算法（即不使用随机性的算法），能够以亚指数时间统计这类难题的所有可满足赋值。这意味着工作量的增长慢于变量数的任何指数函数。由于统计解的数量比判断是否存在至少一个解更难，这一结果也顺带解决了判定问题。

OpenAI称其AI于10月16日发现了该反证，并于10月17日在Lean（一种可机械化验证每个逻辑步骤的软件）中完成形式化。论文及形式化结果已在GitHub上发布。OpenAI表示，此举延续了本月早些时候发布的722份数学手稿，其中仅162份包含经计算机验证的主要结果。正是这种可机器验证的格式，使独立研究者能够自行核实论证的每一个步骤。

Impagliazzo、Paturi和麻省理工学院教授Ryan Williams正在牵头对该声明进行独立审查。他们在一份公开信中告诫称，不应把他们的参与解读为认可。

“我们的参与不应被视作对该声明的认证，”三人写道，并补充说，“如此重大的结果需要审慎的独立审查，也需要认识到他人可以重构、质疑并在此基础上继续研究。”

OpenAI表示，参与者未签署任何保密协议且均为无偿工作。公司还同意公开所有原始数据，并出资举办一场围绕该结果的会议。

其实际影响仍不确定。“找到这样的算法，并将理论进展转化为实用改进，还需要大量进一步的研究，”OpenAI写道。论文本身也指出，该结果并不能证明复杂度类NP中的所有问题都能以亚指数时间求解。

这意味着P与NP问题仍未解决。P由计算机能够高效求解的问题组成，而NP由其候选解可以被高效检验的问题组成。悬而未决的问题是：答案能被高效检验的问题，是否也都能被高效求解。

Anthropic于10月26日加入这场讨论，发布了一篇署名Claude的论文，题为“A 2^o(n) Time Algorithm for 3-SAT”。该代码仓库同样涉及ETH问题，称该算法由内部研究型Claude模型发现，并补充说“该结果纯粹是渐近性的，对实践中求解公式没有任何说明”。

Claude曾于9月在Lean中形式化费马大定理。数学家Terence Tao此前已就AI研究可能相互重叠发出警告，他在9月写道：“我们现在已经看到，甚至仅是有人正在研究某个问题的传闻，就可能引发大量由AI驱动的研究力量，在原研究项目有时间充分发挥其潜力之前就将其抹平。”

OpenAI近期向Simons Foundation捐赠的500万美元将用于资助研讨会、会议和专项计划，帮助研究者审查并在AI产出的结果基础上继续研究。

来源：Decrypt