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.
Copyright © 2023 Author(s) retain the copyright of this article.
This article is published under the terms of the Creative Commons Attribution License 4.0