Ryan Williams 谈为何当年怀疑 ETH：已知 c^n 系列结果让蛮力下界存疑
rrwilliams · x · 2026-10-28
在被问及「除了聪明人一直没找到更快算法之外，还有什么理由相信 ETH 为真」时，Williams 回应：已有系列论文将 SAT 的指数从 2^n 降到更小的 c^n，「不存在比蛮力更好的算法」这一前提其实早已不成立。他坦承这些已知算法的扩展（如基于 resolution 的方法）确实被证明受限于 ETH，但他认为这些理由并不充分，因此决定先集中精力反驳 SETH。这条与后续关于 PPSZ 下界的问答构成完整上下文。
所属事件:Williams 与 minilek 辨析 ETH:已知 SAT 算法与下界的关系(6 条相关)→
「研究」频道最新
- OpenBonsai 开源：9B 模型压到约 2GB 三值 GGUF，RTX 5090 五小时完成 — ButtercupLyn100 · 2026-10-29
- Jeva 论文重思 System 1 模型：单次推理可在 2048 个候选中做类型化决策 — AndLukyane · 2026-10-29
- JSSA 稀疏注意力：128K 上下文解码吞吐最高提升 6.43 倍 — pmttyji · 2026-10-29
- AI 发现快过验证机构：AlphaFold 绘 2 亿蛋白结构背后的科研诚信悖论 — mikeflache · 2026-10-29
- FrontierCS 2 排名洗牌：Claude Opus 5.5 居首，DeepSeek 1017 被指退化 — teortaxesTex · 2026-10-29
- 不到 500 美元给开源模型做「宪法」人格训练:grafting 绕开 44 万美元成本 — voooooogel · 2026-10-29