Summary
A SAT 2026 paper titled "New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions" by Sanjay Jain, Junqiang Peng, Frank Stephan, and colleagues presents new upper bounds for Parity-SAT, the problem of deciding whether a Boolean formula has an odd number of satisfying assignments. Parity-SAT is ⊕P-complete and is considered harder than SAT, with classical assumptions implying no algorithms can beat the 2^n or 2^m exponential barriers. The paper reports three results: (1) for bounded-occurrence versions, it breaks the 2^m barrier with an O*(2^{m(1-1/O(d))}) algorithm for formulas with occurrence bound d; (2) for the d=2 special case, it achieves O*(1.1193^n); and (3) using structural generalizations, it reaches O*(1.1052^L) for the general version. All these upper bounds improve on the corresponding exact counting (#SAT) algorithms. The core insight is counterintuitive but correct: deciding whether the count is odd or even is algorithmically easier than counting exactly, because tracking information modulo 2 permits more aggressive branching and reduction rules. Preprint: arXiv:2605.14093 (cs.DS), https://arxiv.org/abs/2605.14093.
SAT asks whether a Boolean formula has any satisfying assignment. Parity-SAT asks whether the number of satisfying assignments is odd — a strictly harder problem (⊕P-complete), which under classical complexity assumptions cannot beat the 2ⁿ or 2ᵐ exponential barriers.
A recent SAT 2026 paper reports three results:
- Breaking the 2ᵐ barrier for the bounded-occurrence version, with an algorithm running in O*(2^{m(1-1/O(d))}), where d is the occurrence bound.
- A d = 2 special case algorithm running in O*(1.1193ⁿ).
- A structural generalization extending to the general version in O*(1.1052^L), where L is the formula length.
All of these upper bounds are better than the corresponding bounds for exact counting (#SAT). The core takeaway: parity has an algorithmic advantage over exact counting — you only need to track information modulo 2, which allows bolder branching and reduction rules.
> Counterintuitive but true: deciding whether the count is odd or even is genuinely easier than counting exactly how many there are.
Paper information
- Title: *New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions*
- Authors: Sanjay Jain, Junqiang Peng, Frank Stephan, et al.
- Venue: SAT 2026
- Preprint: arXiv:2605.14093 (cs.DS)
- Link: https://arxiv.org/abs/2605.14093
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/177620155