奇偶 SAT 比精确计数更容易——新论文突破 2ᵐ 指数屏障

SAT 问题判断公式是否有解。Parity-SAT 判断解的数量是否为奇数——后者更难（⊕P-complete），在经典假设下无法突破 2ⁿ 或 2ᵐ 屏障。

SAT 2026 论文的三个结果：对受限版本突破 2ᵐ 屏障（O*(2^{m(1-1/O(d))})）；d=2 特例 O*(1.1193ⁿ)；利用结构推广到通用版本 O*(1.1052^L)。

所有上界都优于对应的精确计数问题（#SAT）。核心结论：奇偶性比精确计数有算法优势——只需要追踪模 2 信息，可以做更大胆的分支和归约。

反直觉但正确：判断"是奇数还是偶数"真的比"数出具体有多少"容易。

论文信息

• 标题：New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
• 作者：Sanjay Jain, Junqiang Peng, Frank Stephan 等
• 发表：SAT 2026
• 预印本：arXiv:2605.14093 (cs.DS)
• 论文链接：https://arxiv.org/abs/2605.14093

#ParitySAT #SAT #Algorithms #Complexity #FeynmanLearning #智柴