ETH 指数时间假设疑被证伪引发热议

10 月 27 日前后,复杂度理论圈密集流传一项重大理论结果:k-SAT 可在 2^(n/log n) 时间内求解,即指数时间假设(ETH)不成立。消息源头可追溯到 Scott Armstrong 关于「ETH 不成立」的宣告,经 mcarbin 等人转发断言「ETH 已被证明为假」后在社区扩散,MIT CSAIL 一条问答帖下被刷屏。开发者 Eric Zhang(ekzhang1)发推称深感震撼,表示 SAT 求解需要指数时间是第一堂 CS 课就学的常识,自己从未质疑过。

已确认

• 流传的结果为:k-SAT 存在 2^(n/log n) 时间算法,即 ETH 被证伪;该界在技术上属于亚指数级。
• bzogrammer 给出技术性解读:ETH 是比 P≠NP 更强的命题,被证伪有些意外,但并不会推翻太多既有结论。
• 圈内存在争议:有人认为这是史上最大理论成果之一,但 verbine 等人反驳称该结果并不算意外,k-SAT 本身地位从来不算大事,并认为 10 月 6 日发布的另一成果比 ETH 被证伪更重磅。

尚未确认

• 该证明本身的正确性与正式发表状态在帖子材料中未见确认,多为社区转述与讨论。

为什么重要

• ETH 是算法课常识级别的下界假设,其被击穿打破了长期习以为常的直觉。
• @rebelcrayon 指出,这一突破与此前 O(n log n) 乘法算法类似但后果更严重:乘法最多只能省掉 log n 因子,而 ETH 被击穿后「后续空间很大」,部分安全假设可能需要全面重审。

2026-10-27 ~ 2026-10-27 · 5 条相关

事件全程(共 5 集)→

• 第 1 集:OpenAI 宣称 AI 连获三项科学发现，含证伪 ETH(2026-10-27,69 条)
• 第 2 集:Brockman 回应 AI 数学热:P 大概率仍不等于 NP(2026-10-27,6 条)
• 第 3 集:ETH 指数时间假设疑被证伪引发热议(2026-10-27,5 条)
• 第 4 集:Anthropic 称 Claude 自主发现推翻 ETH 的 3-SAT 算法(2026-10-27,8 条)
• 第 5 集:AI 求解 ETH 难题引质疑：形式化证明与文本不匹配(2026-10-27,2 条)

• 复杂度研究者解读 ETH 证伪：比 P≠NP 更强，但实际影响有限 — burny_tech · 2026-10-27
• 理论 CS 大新闻之争:10月6日发布比 ETH 被证伪更重磅 — burny_tech · 2026-10-27
• ETH 被证伪的消息开始在圈内扩散，MIT CSAIL 问答帖下被刷屏 — burny_tech · 2026-10-27
• 开发者惊传指数时间假设 ETH 被推翻，SAT 复杂度常识或遭颠覆 — akbirthko · 2026-10-27
• 【源头】学界疑似突破猜想下界,研究者警告安全假设或需全面重审 — IgorCarron · 2026-10-27