New Algorithms for #2-SAT and #3-SAT

Peng, Junqiang; Sheng, Zimo; Xiao, Mingyu

doi:10.24963/ijcai.2025/297

New Algorithms for #2-SAT and #3-SAT

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 2666-2674.

https://doi.org/10.24963/ijcai.2025/297

Keywords

Constraint Satisfaction and Optimization: CSO: Satisfiabilty

Abstract

The #2-SAT and #3-SAT problems involve counting the number of satisfying assignments (also called models) for instances of 2-SAT and 3-SAT, respectively. In 2010, Zhou et al. (https://doi.org/10.1609/aaai.v24i1.7537) proposed an O*(1.1892^m)-time algorithm for #2-SAT and an efficient approach for #3-SAT, where m denotes the number of clauses. In this paper, we show that the weighted versions of #2-SAT and #3-SAT can be solved in O*(1.1082^m) and O*(1.4423^m) time, respectively. These results directly apply to the unweighted cases and achieve substantial improvements over the previous results. These advancements are enabled by the introduction of novel reduction rules, a refined analysis of branching operations, and the application of path decompositions on the primal and dual graphs of the formula.

Junqiang Peng, Zimo Sheng, and Mingyu Xiao. 2025. New Algorithms for #2-SAT and #3-SAT. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 2666–2674. https://doi.org/10.24963/ijcai.2025/297

@inproceedings{ijcai2025p297,
  title     = {New Algorithms for #2-SAT and #3-SAT},
  author    = {Peng, Junqiang and Sheng, Zimo and Xiao, Mingyu},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {2666--2674},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/297},
  url       = {https://doi.org/10.24963/ijcai.2025/297},
}

TY  - CPAPER
TI  - New Algorithms for #2-SAT and #3-SAT
AU  - Peng, Junqiang
AU  - Sheng, Zimo
AU  - Xiao, Mingyu
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 2666
EP  - 2674
DO  - 10.24963/ijcai.2025/297
UR  - https://doi.org/10.24963/ijcai.2025/297
ER  -