Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Solving Restricted Versions of #SAT Faster than : Algorithms and Lower Bounds
Sanjay Jain, Junqiang Peng, Frank Stephan +1
Under the Strong Exponential Time Hypothesis (SETH), for any constant , the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be…
cs.DS2026
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 P-complete problem, it represents a fundame…