Abstract
Propositional Model Counting (#SAT) is a fundamental problem in computer science with applications ranging from probabilistic inference to planning. While SAT solvers have long benefited from preprocessing, #SAT requires specialized techniques that preserve the number of satisfying assignments. This paper introduces pmc, a preprocessor that implements a suite of count-preserving simplifications. Our evaluation on 1,342 benchmark instances demonstrates that pmc significantly improves the performance of both direct model counters and knowledge compilation tools, often reducing computation time and output size by orders of magnitude.
Introduction
In computational logic, Boolean Satisfiability (SAT) asks if a formula has at least one solution. Propositional Model Counting (#SAT) goes further, asking for the exact number of solutions. While SAT is NP-complete, #SAT belongs to the #P-complete complexity class, making it significantly more challenging in practice.
Preprocessing is a standard step in SAT solving, where a formula is simplified before being passed to a solver. However, many common SAT techniques, such as the pure literal rule, are inapplicable to #SAT because they do not preserve the total model count. This research addresses the gap by developing and evaluating pmc, a specialized preprocessor designed to simplify formulas while maintaining their model counts.
Methodology: The pmc Preprocessor
The authors implemented pmc to iteratively apply several simplification techniques. These are categorized into two types:
- Equivalence-Preserving (
eq): These techniques simplify the formula while maintaining logical equivalence. Examples include Vivification (using Boolean Constraint Propagation to prune redundant literals), Occurrence Reduction, and Backbone Identification (identifying literals that must be true in every solution). - Count-Preserving (
#eq): These techniques may alter the logic of the formula but are guaranteed to preserve the total number of satisfying assignments. A primary example is Gate Replacement, which identifies structural patterns like XOR and AND gates and replaces them with more efficient representations.
Because #SAT is inherently more difficult than SAT, the authors argue that more "aggressive" and computationally expensive preprocessing (like backbone identification) is justified, as the time saved during the counting phase far outweighs the preprocessing cost.
Experimental Evaluation
The pmc tool was evaluated using a comprehensive dataset of 1,342 CNF instances from 19 different families in the SAT LIBrary. The experiments focused on the impact of preprocessing on two main types of tools:
- Direct Counters: Represented by
Cachet, which counts models directly. - Knowledge Compilers: Represented by
C2D, which compiles the formula into a deterministic Decomposable Negation Normal Form (d-DNNF).
Key Results and Discussion
Impact on Knowledge Compilation
For compilation-based approaches like C2D, preprocessing is crucial. The experiments show that eq preprocessing leads to substantial reductions in both the time required for compilation and the size of the resulting d-DNNF.
As shown in Figure 6, the time required for C2D to compile formulas is significantly reduced across a wide range of benchmarks. In many cases, the speedup is more than an order of magnitude. Furthermore, the resulting compiled forms are much more compact.
Figure 1 illustrates the space savings achieved. Smaller d-DNNF sizes are highly desirable as they facilitate faster downstream queries in probabilistic inference tasks.
Performance of Direct Counters
For direct counters like Cachet, the more aggressive #eq preprocessing proved highly effective. By incorporating gate identification and replacement, Cachet was able to solve 132 additional instances within the time limit compared to the baseline without preprocessing.
Efficiency of the Preprocessor
A critical finding is that pmc itself is extremely efficient. For approximately 80% of the tested instances, the preprocessing phase completed in less than one second. Even when accounting for the time spent on preprocessing, the cumulative time to solve the benchmarks was drastically reduced. For example, the total time for C2D across the benchmark suite dropped from over 123,000 seconds to approximately 53,000 seconds when using eq preprocessing.
Conclusion
The pmc preprocessor demonstrates that adapting SAT simplification techniques for model counting is a powerful strategy for tackling #P-complete problems. By distinguishing between equivalence-preserving and count-preserving methods, researchers can tailor preprocessing to their specific solver or compiler. Future work will explore the impact of these techniques on approximate counting and investigate the relationship between preprocessing and theoretical metrics like treewidth.
Summary updated