---
title: "New Algorithms for #2-SAT and #3-SAT"
authors:
  - "Junqiang Peng"
  - "Zimo Sheng"
  - "Mingyu Xiao"
doi: "10.24963/ijcai.2025/297"
url: "https://ijcai.org/proceedings/2025/297"
pdf: "https://ijcai.org/proceedings/2025/0297.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "2666-2674"
track: "Main Track"
keywords:
  - "Constraint Satisfaction and Optimization: CSO: Satisfiabilty"
---

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

Junqiang Peng, Zimo Sheng, Mingyu Xiao

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 2666-2674. DOI: [10.24963/ijcai.2025/297](https://doi.org/10.24963/ijcai.2025/297)

## 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.