Ryan Williams 回应 SETH 反驳论文追问：旧算法不满足下界条件
rrwilliams · x · 2026-10-29
理论计算机科学家 Ryan Williams 与 minilek（Quanta 相关）就其反驳 SETH（强指数时间假设）的新工作展开技术问答。minilek 追问：此前最优算法（如 SAT 求解的 PPSZ）是否满足那条针对 resolution 类方法的下界条件？Williams 回答「是」，并解释：此前已知已知算法的扩展仍「服从」ETH——例如基于 resolution 的方法（涵盖现代 SAT 求解器的大部分行为）已被证明无法突破，但他当年觉得这些理由不够强，所以选择先反驳 SETH 再考虑 ETH。
所属事件: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