New algorithms for Exact Satisfiability

The Exact Satisfiability problem is to determine if a CNF-formula has a truth assignment satisfying exactly one literal in each clause; Exact 3-Satisfiability is the version in which each clause contains at most three literals. In this paper, we present algorithms for Exact Satisfiability and Exact 3-Satisfiability running in time O(20.2325n) and O(20.1379n), respectively. The previously best algorithms have running times O(20.2441n) for Exact Satisfiability (Methods Oper. Res. 43 (1981) 419-431) and O(20.1626n) for Exact 3-Satisfiability (Annals of Mathematics and Artificial Intelligence 43 (1) (2005) 173-193 and Zapiski nauchnyh seminarov POMI 293 (2002) 118-128). We extend the case analyses of these papers and observe that a formula not satisfying any of our cases has a small number of variables, for which we can try all possible truth assignments and for each such assignment solve the remaining part of the formula in polynomial time.