#SAT 破防：四学者给出打破 2^m 时间屏障的新算法
IgorCarron · x · 2026-10-15
arXiv 新论文《Solving Restricted Versions of #SAT Faster than 2^m: Algorithms and Lower Bounds》（Sanjay Jain、Junqiang Peng、Frank Stephan、Mingyu Xiao）突破了 #SAT 计数问题的复杂度屏障。
背景：在强指数时间假设（SETH）下，#SAT（统计 CNF 公式满足赋值数）无法在 O((2-ε)^n) 或 O((2-ε)^m) 时间内解决，而暴力搜索和容斥原理分别给出 O(2^n) 和 O(2^m) 算法。此前已知当子句长度 k 或变量出现次数 d 为常数时 2^n 屏障可破，但 2^m 屏障一直未能突破。
成果：
- 对 #k-SAT 给出 O(2^(m(1-1/O(k)))) 时间算法，对任意常数 k 打破 2^m 屏障
- 对 #2-occ-SAT（含图中边覆盖计数为特例）给出 O(2^(mω/3)) 算法，ω<2.3714 为矩阵乘法指数
- 并证明了相应的下界
「研究」频道最新
- lateinteraction：RLVR 就是 RL，奇怪的其实是 RLHF — lateinteraction · 2026-10-15
- 工具使用概念比想象更老：LaMDA 论文 2022 年就已顺带提及 — soldni · 2026-10-15
- 数学家撰文解读 OpenAI 372 定理冲击:数学前沿是自组织临界沙堆 — littmath · 2026-10-15
- RoPE 长文本失效有理论证明,免训练诊断工具提分最高 25% — zhaofeng_wu · 2026-10-15
- OpenAI 证明引连锁反应，Bhargava 证明原根正密度定理 — Singularitarian · 2026-10-15
- Applied Compute 推出 Spork：国际象棋解题率较 GRPO 提升 100% — ypatil125 · 2026-10-15