New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions

Sanjay Jain, Junqiang Peng, Frank Stephan +2

Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical $\oplus$P-complete problem, it represents a fundame…