ETH 被证伪：OpenAI 证明的简化版
A simplified proof of ETH is False [pdf]
这篇论文提出了一种确定性 3-SAT 算法，旨在反驳扩展指数时间假设（ETH）。作者 Shiva Kintali 对 OpenAI 之前的证明进行了简化阐述，结合了稀疏化、有界出现、谱替换和理性插值等技术。核心思路是将变量分组，通过代数变形移除组间联系，利用多项式插值恢复满足赋值计数。该算法能在任意小的指数率内解决 3-SAT 问题，直接挑战了 ETH 关于 3-SAT 需要指数时间复杂度的断言。
我们给出一个确定性 3-SAT 算法，使用 Cε(n + m + 1) cε 2εn 位运算，从而驳斥了 ETH。