New Algorithms for #2-SAT and #3-SAT
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911066357760000 |
|---|---|
| author | Peng, Junqiang Sheng, Zimo Xiao, Mingyu |
| author_facet | Peng, Junqiang Sheng, Zimo Xiao, Mingyu |
| contents | 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. proposed an $\mathcal{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 $\mathcal{O}^*(1.1082^m)$ and $\mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14504 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Algorithms for #2-SAT and #3-SAT Peng, Junqiang Sheng, Zimo Xiao, Mingyu Data Structures and Algorithms 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. proposed an $\mathcal{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 $\mathcal{O}^*(1.1082^m)$ and $\mathcal{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. |
| title | New Algorithms for #2-SAT and #3-SAT |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.14504 |