理论家辨析：PPSZ 等已知 SAT 算法是否落在 ETH 下界约束内
minilek · x · 2026-10-29
minilek（ACM CSSI 创始人 Donald Knuth 传记作者、Duke 教授）与复杂度理论家 Ryan Williams 在 X 上讨论：已知指数时间下界（如 2^{o(n)} 不可能）只对受限算法类成立（如基于归结的方法），他追问 PPSZ 等已知最优理论算法是否也落入这些受限类。Williams 回应此前已知对已知算法的扩展仍遵守 ETH，归结法（涵盖现代 SAT 求解器大部分行为）不可行，但他认为需先驳倒 SETH 再谈 ETH。
所属事件:Williams 与 minilek 辨析 ETH:已知 SAT 算法与下界的关系(6 条相关)→
「研究」频道最新
- AReA 免训练方法让 Qwen Image、Flux 出 6K 大图 — linoy_tsaban · 2026-10-29
- 研究发现 Llama 隐状态呈 3D 螺旋,暗合元素周期表结构 — burny_tech · 2026-10-29
- 研究者窥探 Mamba 神经元:可定位并放大单个词的触发机制 — burny_tech · 2026-10-29
- Apple 招 PhD 实习生，主攻视频 LLM 的落地推理与端侧模型 — HildeKuehne · 2026-10-29
- NeurIPS 新工作 MASEM:面向目标条件 RL 的多样化机器人状态采样 — KyleMorgenstein · 2026-10-29
- 无需读论文：四步用本地小模型和 Claude 玩转 mech-interp — burny_tech · 2026-10-29