OpenAI 声称推翻指数时间假设，研究人员正独立核查

OpenAI 声称其 AI 推翻了指数时间假设（ETH），引发了加密社区的误读和调侃。一些 X 用户以为这与以太坊有关，但这里的 ETH 指的是计算机科学中的一个猜想，与以太坊、其价格或联合创始人 Vitalik Buterin 无关。

OpenAI 发布了一篇长达 67 页的论文，称其 AI 找到了绕过这一假设的方法。指数时间假设由计算机科学家 Russell Impagliazzo、Ramamohan Paturi 和 Francis Zane 于 1999 年提出，认为经典逻辑难题 3-SAT 无法比枚举所有组合快得多地求解。OpenAI 表示，数百篇论文依赖该假设，论证图论、计算生物学、数据库和几何学中的问题无法快速解决。

论文描述了一种确定性算法，可以在次指数时间内计算这类难题的所有满足赋值，也就是所有符合条件的解。由于计算解的数量比判断是否存在解更难，若该算法成立，较简单的判定任务也能随之解决。OpenAI 称，AI 于 10 月 16 日发现反证，并于 10 月 17 日在 Lean 中完成形式化验证；论文标注日期为 10 月 17 日，并于 10 月 25 日修订。

指数时间假设的提出者 Impagliazzo、Paturi 以及 MIT 的 Ryan Williams 正在开展独立审查。三人在公开信中强调，他们的参与不应被视为对这一结论的认证，并指出，如此重大的成果需要谨慎、独立的审查，也需要让其他研究者能够重现、质疑并在此基础上继续研究。