New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter

Junping Zhou, Minghao Yin, Chunguang ZhouAAAI 2010 · DOI

Abstract

This paper establishes the first rigorous worst-case upper bounds for #2-SAT and #3-SAT using the number of clauses ($m$) as the complexity parameter. By introducing a novel "five-vertex principle" for formula simplification and utilizing constraint graph analysis, the authors achieve time complexity bounds of $O(1.1892^m)$ for #2-SAT and $O(1.4142^m)$ for #3-SAT.

Introduction

In computer science, the Satisfiability (SAT) problem asks if there is an assignment of truth values that makes a boolean formula true. The #SAT (pronounced "sharp-SAT") problem is significantly more challenging: it asks how many such assignments exist. While SAT is NP-complete, #SAT is #P-complete, making it computationally daunting but essential for fields like probabilistic inference and artificial intelligence.

Historically, researchers have analyzed the complexity of #SAT algorithms based on the number of variables ($n$). However, the actual difficulty of an instance is also heavily influenced by the number of clauses ($m$). While SAT algorithms had been analyzed using $m$ as a parameter, doing so for #SAT remained an open problem. This research provides the first rigorous worst-case upper bounds for #2-SAT and #3-SAT using $m$ as the complexity parameter.

Methodology

The authors utilize a DPLL-style algorithm (Davis-Putnam-Logemann-Loveland), which is a backtracking-based search. Their approach, specifically the $MC_2$ algorithm, relies on several primary innovations:

Algorithm $MC_2(F, R)$ for model counting.
  1. Constraint Graph Analysis: Boolean formulas are represented as undirected graphs where variables are vertices and edges represent shared clauses. This allows the use of graph theory to identify "bottlenecks" and simplify the formula.
  2. The Five-Vertex Principle: This is a new reduction rule specifically for #2-SAT. It identifies specific local structures in the constraint graph (where a variable has a degree of 3 and specific neighborhood properties) and allows the algorithm to eliminate variables more efficiently than standard branching.
  3. Recursive Reduction for #3-SAT: To solve #3-SAT, the algorithm branches on variables that appear most frequently in 3-literal clauses. This process continues until the formula is reduced to a 2-SAT instance, at which point the optimized #2-SAT solver takes over.

The complexity is measured using a branching tree analysis, where the "branching number" determines the exponential growth rate of the algorithm's runtime.

Key Insights and Ideas

  • Shifting the Parameter: The core insight is that $m$ (clauses) is a viable and useful metric for #SAT complexity. This provides a different perspective on problem "hardness" that complements variable-based analysis.
  • Structural Simplification: The "five-vertex principle" demonstrates that we don't always have to branch on every variable. By recognizing specific graph patterns, we can solve sub-components of the formula in polynomial time, effectively "skipping" steps in the exponential search.
Local graph structure used for formula simplification in the #2-SAT algorithm.
  • The Power of Reduction: The strategy for #3-SAT shows that the efficiency of higher-order SAT solvers is deeply tied to how quickly they can be reduced to lower-order versions (like #2-SAT).

Key Results

The paper establishes two major new upper bounds for the time complexity of model counting:

  • #2-SAT: $O(1.1892^m)$
  • #3-SAT: $O(1.4142^m)$

Even a small reduction in the base of the exponent (e.g., from $O(2^m)$ to $O(1.4142^m)$) represents a massive increase in the size of problems that can be solved within a reasonable timeframe. These results represented the best-known upper bounds for these problems using the number of clauses as the parameter at the time of publication. As a theoretical paper, these results are derived through mathematical proofs and recurrence relations rather than experimental trials.

Limitations and Future Work

  • Worst-Case vs. Average-Case: This study focuses on the worst-case scenario. In practice, many real-world #SAT instances have structures that allow them to be solved much faster than these bounds suggest.
  • Polynomial Factors: The analysis ignores polynomial-time overhead (the "poly(F)" factor), focusing strictly on the exponential growth.
  • Higher-Order SAT: Extending these clause-based bounds to general #k-SAT (where $k > 3$) remains a direction for future research.

Summary updated

BibTeX
@inproceedings{zhou2010new,
  author = {Junping Zhou and Minghao Yin and Chunguang Zhou},
  title = {{New Worst-Case Upper Bound for \#2-SAT and \#3-SAT with the Number of Clauses as the Parameter}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7537},
}
Figure