Summary
SAT asks whether a Boolean formula has a satisfying assignment; Parity-SAT asks whether the number of satisfying assignments is odd. Parity-SAT is ⊕P-complete and, under standard assumptions, was believed to be stuck behind the 2^n / 2^m exponential barriers. A SAT 2026 paper, 'New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions' by Sanjay Jain, Junqiang Peng, Frank Stephan and colleagues (preprint arXiv:2605.14093), presents three results: (1) for bounded-occurrence versions, an O*(2^{m(1-1/O(d))}) algorithm that breaks the 2^m barrier; (2) an O*(1.1193^n) algorithm for the d=2 special case; (3) a structural generalization achieving O*(1.1052^L) for the general version. All bounds improve on the corresponding exact counting problem (#SAT). The core insight is that parity has algorithmic advantages over exact counting: tracking information modulo 2 enables bolder branching and reductions, making it genuinely easier to decide whether the solution count is odd or even than to count solutions exactly.
SAT asks whether a Boolean formula has a satisfying assignment. Parity-SAT asks whether the number of satisfying assignments is odd — a strictly harder problem (⊕P-complete), which under classical assumptions was not expected to break the 2^n or 2^m exponential barriers.
A SAT 2026 paper presents three results:
- Bounded-occurrence versions: breaks the 2^m barrier with an O*(2^{m(1-1/O(d))}) algorithm.
- d=2 special case: an O*(1.1193^n) algorithm.
- General version via structural parameters: O*(1.1052^L).
All of these upper bounds beat the corresponding exact counting problem (#SAT). The core conclusion: parity has an algorithmic advantage over exact counting — you only need to track information modulo 2, which permits bolder branching and reduction rules.
> Counterintuitive but true: deciding "odd or even" is genuinely easier than "counting exactly how many."
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