Williams 与 minilek 辨析 ETH:已知 SAT 算法与下界的关系

10 月 28 日至 29 日,Duke 教授 minilek(Donald Knuth 传记作者、ACM CSSI 创始人)与理论计算机科学家 Ryan Williams 在 X 上围绕指数时间假设(ETH)展开多轮技术讨论,起因是 Williams 反驳强指数时间假设(SETH)的新工作引发的追问。

已确认

• minilek 的核心疑问:除了「聪明人一直没找到更快算法」这一经验事实外,历史上是否有实质性理由相信 ETH 应当成立。
• Williams 承认,一系列论文已把 SAT 的指数底数从 2^n 压到更小的 c^n(帖子提及平凡 1.913^n 算法),因此「不存在比蛮力更好的算法」这一前提其实早已不成立,这也是他当年对 ETH 持怀疑态度的原因之一。
• 针对 minilek 追问已知最优 SAT 算法(如 PPSZ 类 (2-ε)^n 亚指数算法)是否落入某条下界约束:Williams 答复称,已知算法的扩展已知仍遵守 ETH;指数时间下界(如排除 2^{o(n)} 算法)只对受限算法类成立,例如归结(resolution)类方法——这类方法刻画了现代 SAT 求解器的主要行为。
• minilek 还询问这些已知的 (2-ε)^n 算法能否被某个宽泛而自然的算法类统一涵盖,讨论涉及细粒度复杂度(SETH 相关)框架。

为什么重要

• ETH/SETH 是大量条件性下界(即「除非 ETH 失败,否则问题 X 没有快算法」)的基石。若其根基动摇,依赖它的 hardness 结果都需要重新审视。
• 这场对话厘清了一个常见误解:下界并非对所有算法成立,而是针对归结等受限模型;现代 SAT 求解器恰好大体落在这类模型内,这使得下界对实践仍有解释力。PPSZ 等算法与下界条件的关系,正是判断「ETH 是否被现有技术威胁」的关键边界。

2026-10-28 ~ 2026-10-29 · 6 条相关

• 【源头】指数时间假设还站得住吗:从平凡 1.913^n 算法谈起 — minilek · 2026-10-28
• 【源头】Ryan Williams 谈为何当年怀疑 ETH：已知 c^n 系列结果让蛮力下界存疑 — rrwilliams · 2026-10-28
• 追问 PPSZ：归结法下界是否覆盖此前最优 SAT 算法 — minilek · 2026-10-29
• 【源头】Ryan Williams 回应 SETH 反驳论文追问：旧算法不满足下界条件 — rrwilliams · 2026-10-29
• 理论家辨析：PPSZ 等已知 SAT 算法是否落在 ETH 下界约束内 — minilek · 2026-10-29
• minilek 追问 PPSZ 类算法：已知 2^(-εn) 亚指数算法能否归入一个自然算法类 — minilek · 2026-10-29