The worst case upper bounds in #3-SAT with the number of clauses as the parameter
Junping Zhou, Zhiqiang Ma, Minghao Yin · International Journal of the Physical Sciences · 2011
The rigorous theoretical analyses of algorithms for #SAT problem had been proposed in recent years. However, as far as we know, all algorithms for solving #SAT had been analyzed using the number of variables as parameter. In this paper, an algorithm for #3-SAT with rigorous complexity analyses using the number of clauses as parameter was presented. By analyzing the algorithm, the worst-case upper bound O(1.7614m) was obtained, where m was the number of clauses. Key words: Upper bound, #3-SAT, model counting, complexity analyses.