宣称指数时间假设被推翻：3SAT 可在亚指数时间求解

cephaloform · x · 2026-10-27

danintheory 宣布在调和分析、复杂性理论与量子场论三个方向取得新发现，其中复杂度理论部分被 hallerite 解读为：指数时间假设（ETH）被推翻——即 3SAT 最坏情况可以亚指数时间求解。若 ETH 为真则隐含 P≠NP，因此这是对计算未来「乐观」的结果。

转发的讨论补充了精确表述：按 Ryan Williams 的说法，新结果给出 3SAT 在 n 变量上约 exp(n/(log n)^{1/2+o(1)}) 时间的算法，渐近低于一切 2^(cn)，但并非多项式时间，论文本身也声明这并不意味着所有 NP 问题都可在亚指数时间解决。该声明尚属新发布，结论有待领域验证。