New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter
Abstract
The rigorous theoretical analyses of algorithms for #SAT have been proposed in the literature. As we know, previous algorithms for solving #SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving #SAT instances depends not only on the number of variables, but also on the number of clauses. Therefore, it is significant to exploit the time complexity from the other point of view, i.e. the number of clauses. In this paper, we present algorithms for solving #2-SAT and #3-SAT with rigorous complexity analyses using the number of clauses as the parameter. By analyzing the algorithms, we obtain the new worst-case upper bounds O(1.1892m) for #2-SAT and O(1.4142m) for #3-SAT, where m is the number of clauses.
Cite
Text
Zhou et al. "New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter." AAAI Conference on Artificial Intelligence, 2010. doi:10.1609/AAAI.V24I1.7537Markdown
[Zhou et al. "New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter." AAAI Conference on Artificial Intelligence, 2010.](https://mlanthology.org/aaai/2010/zhou2010aaai-new/) doi:10.1609/AAAI.V24I1.7537BibTeX
@inproceedings{zhou2010aaai-new,
title = {{New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter}},
author = {Zhou, Junping and Yin, Minghao and Zhou, Chunguang},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2010},
pages = {217-222},
doi = {10.1609/AAAI.V24I1.7537},
url = {https://mlanthology.org/aaai/2010/zhou2010aaai-new/}
}