Introduction
Counting the number of satisfying assignments for a Boolean formula in Disjunctive Normal Form (#DNF) is a fundamental problem in computer science with broad applications in network reliability and probabilistic databases. While satisfiability for DNF is trivial, exact counting is #P-complete. Consequently, researchers rely on Fully Polynomial Randomized Approximation Schemes (FPRAS), which provide a $(1 \pm \epsilon)$ estimate with high confidence $(1 - \delta)$.
Historically, Monte Carlo methods like the Karp-Luby (KL) counter have been the standard. Recently, hashing-based schemes like DNFApproxMC emerged, offering a different approach by partitioning the solution space using 2-universal hash functions. However, these methods often carried "polylog" theoretical overheads. This work bridges the gap between theory and practice by optimizing hashing-based schemes and conducting the first comprehensive empirical comparison of #DNF algorithms.
Methods and Innovation: ReverseSearch
A primary bottleneck in hashing-based methods is finding the optimal number of hash constraints to isolate a manageable number of solutions in a "cell." Previous symbolic implementations used binary search, introducing a logarithmic factor to the complexity.
The authors introduce ReverseSearch, a novel search procedure that explores the solution space more efficiently. By integrating ReverseSearch, the theoretical complexity of hashing-based counting is reduced to $O(mn \log(1/\delta)/\epsilon^2)$, matching the best-known bounds for Monte Carlo methods. Empirically, ReverseSearch provides a significant performance boost over traditional binary search for symbolic implementations.
Empirical Evaluation
To evaluate these algorithms, the authors generated a diverse benchmark suite of 1,080 DNF formulas, varying the number of variables (up to 100,000), the number of cubes (up to 800,000), and the "cube-width" ($w$). Cube-width is a critical parameter as it determines solution density, which significantly impacts algorithm performance.
Key Results
The empirical study revealed a stark contrast between theoretical complexity and practical robustness. While some algorithms have better worst-case bounds, their performance varies wildly based on formula structure.
- Robustness of Hashing:
DNFApproxMCemerged as the most robust algorithm, solving all 1,080 benchmarks within the 500-second time limit. In contrast, every other algorithm, including the widely-used KLM Counter, failed on at least 100 instances. - Sensitivity to Density: Monte Carlo methods and symbolic hashing methods are highly sensitive to solution density. In sparse instances (low cube-width), these methods struggle to find valid samples, leading to timeouts.
DNFApproxMCremains consistent across these variations. - Theory vs. Practice: Interestingly, for the non-symbolic
DNFApproxMC, a simple linear search outperformed more complex strategies due to efficient internal data structures that buffer solutions.
Conclusion
This research demonstrates that theoretical complexity is not always a reliable predictor of practical performance for #DNF counting. By introducing ReverseSearch, the authors aligned hashing-based methods with the best theoretical bounds. More importantly, their empirical study identifies DNFApproxMC as the most reliable "safe bet" for general-purpose DNF counting, particularly when solution density is unknown. Future work should focus on leveraging structural properties of DNF formulas to further optimize these approximation schemes.
Summary updated