OpenAI 论文宣称推翻 ETH 并给出 3-SAT 亚指数算法

OpenAI 发布论文《The Exponential Time Hypothesis Is False》，声称给出一个针对任意固定 k≥2 的 k-CNF 精确计数确定性算法，运行时间为 (n+m)^{Ok(1)} · 2^{n/(log n)^{1/2+o(1)}}，空间为多项式级。该算法也可用于判定 3-SAT 是否可满足，论文共 64 页，相关声明仍待学界检验。