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