New upper bound for the #3-SAT problem
We present a new deterministic algorithm for the #3-SAT problem, based on the DPLL strategy. It uses a new approach for counting models of instances with low density. This allows us to assume the adding of more 2-clauses than in previous algorithms. The algorithm achieves a running time of O(1.6423") in the worst case which improves the current best bound of O(1.6737") by Dahllof et al. (c) 2007 Elsevier B.V. All rights reserved.
analysis of algorithms satisfiability counting solutions