OpenAI 预印本声称 3-SAT 可亚指数求解，挑战指数时间假设

cephaloform · x · 2026-10-27

一条转推指向 GitHub 上 Vladimir Reshetnikov 的 ProveIt 仓库中的 SubexponentialSAT 项目，该项目收集了「3-SAT（乃至 #k-SAT）可在 2^{o(n)} 时间内求解」的相关主张。若成立，将推翻 Impagliazzo 与 Paturi 提出的指数时间假设（ETH），即存在某个 δ>0 使 O(2^{δn}) 时间的 3-SAT 算法不可能存在。

核心材料是一份 OpenAI 预印本《The Exponential Time Hypothesis is False》（2026-10-25），仓库收录了 34 份基于该预印本论证的研究包。需注意：仓库明确声明所有内容均未经形式化验证——尚无 Lean 或 Rocq 形式化开发，证明、常数与验证声明均为作者自述，也没有任何包声称实现了端到端 SAT 求解器或实测加速。转推者感叹「看 3SAT 的系数在缩小」。