封面为 AI 生成的概念示意；迷宫与光路是比喻，不是算法结构、真实实验或性能结果。
- 解读日期：2026-10-27
- 资料截止：2026-10-27 20:31:22（北京时间，Asia/Shanghai）
10 月 26 日，OpenAI 宣布其内部模型给出了指数时间假设（ETH）的反驳，并公开自然语言手稿及 Lean 形式化材料。这是值得认真检查的重大主张：它可能改变计算机科学对一类问题“究竟有多难”的判断。不过，公开材料、机器核查与学界理解是不同环节。今天最有价值的问题，是这份主张已经提供了什么，又把哪些工作留给了研究者。官方公告
要推翻的，是怎样一道计算边界？
先想象一组开关：每个开关只能取真或假，每条规则要求几个条件至少满足一个，全部规则又必须同时成立。3-SAT 问的，就是每条规则最多涉及三个文字项时，是否存在满足全部规则的开关配置。这里的文字项可以是变量，也可以是它的否定。
ETH 并非说必须逐一试完所有配置，而是断言：以变量数衡量，最坏情况下无法把这类问题普遍降到次指数时间。次指数可记作 ，意思是指数部分相对变量数的比例会随规模增大趋于零，另需计入读取、处理输入的开销。手稿摘要及引言
这份手稿声称完成的任务更强：对于固定子句宽度的公式，精确计算满足条件的配置总数，并使用多项式空间。只要总数大于零，就能回答是否有解。取宽度为三，便触及 ETH 的核心。因此，值得关注的是随规模增长的理论上界，而非某个测试集多答对了几题。
手稿给出了什么思路，日期又该怎样读？
按手稿的方法概览，算法先把逻辑条件写成多项式，再组织精确计数。一个直观出发点是：如果变量能够分成互不牵连的小组，就可以分别计算，再合并结果。真正困难的是跨组依赖；作者尝试用少量共享的线性摘要传递这些依赖，配合插值等代数方法恢复总数。这只是帮助理解的入口，并非对完整证明的替代。手稿第 2 节
时间线同样不能压缩成“今天发现”。OpenAI 称自然语言反驳产于 10 月 16 日，次日完成形式化；公开 PDF 标注 10 月 17 日、10 月 25 日修订；公告日期是 10 月 26 日。公告未给出精确时区时间，本文不据此断言它发生在过去二十四小时内。公告时间线
这些材料也没有给出本文能够据以确认的同行评审录用信息。它们应作为公开研究手稿和待审查证明阅读。
Lean 覆盖的上界，与手稿并不完全相同
Lean 是证明助手：把命题与推导写成形式语言，再检查其逻辑依赖。它为审查提供了比一段流畅说明更具体的对象，但仍需要人判断形式命题是否准确表达了原问题。
OpenAI 的范围说明明确区分了两个层次：Lean 覆盖规范编码输入上的精确计数、次指数时间和多项式空间；10 月 25 日手稿则给出更紧的时间上界。两者指数项相差一个双重对数因子，手稿在子句数至多为变量数固定倍数时还有更强界限。不能把手稿最好的式子直接标成“全部已由 Lean 验证”。形式化范围说明
范围说明中的较宽松上界仍是次指数的，所以这种差别本身并不推翻其反驳 ETH 的方向。审查应继续追问：编码长度如何计入成本，机器模型如何定义，量词是否要求同一个算法处理全部合格输入。本文核对了范围说明和公开命题文件，但没有运行证明检查器，也没有逐步验证整份证明。
另一份证明，不能自动充当复核报告
截至资料截止时，Anthropic 的公开仓库也提供了 Claude 产生的次指数 3-SAT 算法手稿与形式化材料。其说明同样强调结果是渐近理论结论，并明确提醒：机器检查证明，并不自动检查形式命题是否与论文叙述一致。本文读取的是该仓库说明，尚未完成两份证明的技术比较。Anthropic 原始材料
这增加了可研究的材料，却不能简单累计为“两次独立验证”。另一个团队提出同类结论，与外部研究者成功复核第一份论证，是两种证据。它们是否共享关键思路、是否存在相同盲点，仍值得比较。
Russell Impagliazzo、Ramamohan Paturi 与 Ryan Williams 在公开信中说明，参与组织工作不应被当作对主张的认证。他们邀请社区检查论证、解释方法、研究后果，也讨论如何认可核查与简化证明的劳动。致理论计算机科学社区的公开信
这封信提供的是审查立场，不是已完成的正确性结论。本次检索未找到足以据此报告“独立审查已经完成”的材料。
科研读者现在可以关注什么？
首先，次指数仍可能比任何多项式都增长得快，因此这一主张不能被读成已经解决 P 与 NP。其次，手稿自己提醒：一般多项式归约可能放大变量规模，不能由此推出所有 NP 问题都有次指数算法。理论上界也没有给出实际输入上的加速比。手稿第 2 页
即使反驳成立，过去写成“若 ETH 成立，则某算法不存在”的条件定理，也不因此变成错误证明。失去的是直接把前提当作可信依据的理由；要为目标问题设计更快算法，还需要控制归约方向与规模。这是阅读既有论文时应保持的逻辑区分。
本文的判断是：这次事件的重要性足以推动认真审查，但当前最值得等待的成果，是可重建的核查记录、形式命题与自然语言命题的逐项对应，以及能被其他研究者理解和使用的简化论证。当这些材料出现时，我们才能更清楚地区分：AI 提出了一个重要答案，还是已经帮助学界建立了一份可靠的新知识。
参考资料
- OpenAI：Working with academic communities to build scientific understanding，2026-10-26；已读公告正文。
- The Exponential Time Hypothesis is False，标注 2026-10-17、2026-10-25 修订；已读摘要、引言第 1–5 页与方法概览第 7–8 页，视觉核对第 2 页主定理，未审完整证明。
- OpenAI：ETH 的 Lean 形式化范围说明，页面未标独立发布日期；已读全文，并核对其链接的命题文件，未执行验证。
- Anthropic：A subexponential time algorithm for 3-SAT，仓库说明，页面未标独立发布日期；已读说明全文，未读完整论文或运行证明。
- Impagliazzo、Paturi、Williams：Message to the TCS Community on ETH，文档未标独立日期；通过公开文本导出读到正文，10 月 26 日媒体已有链接。该信是审查组织者的一手立场材料。
作者作品推广
除了写技术博客，我也在做一些让日常更有条理的小工具。以下是我独立开发的两款 App，属于作者自有作品推广，欢迎了解：
- 日常收支小记：记录日常收支，安排预算与储蓄目标，让每一笔钱的去向更清楚。在 App Store 了解。
- 一事微光：根据当下的时间和精力选择一个小行动，记录完成后的感受与发现，让日常行动与复盘更容易开始。在 App Store 了解。
更多技术文章与个人作品，欢迎访问我的网站：zffjzz.top。