Not All FPRASs are Equal: Demystifying FPRASs for DNF-Counting (Extended Abstract)

Kuldeep S. Meel, Aditya A. Shrotri, Moshe Y. Vardi

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.

Figure 3: Comparison of SymbolicDNFApproxMC using Reverse Search versus Binary Search. Points below the diagonal indicate that Reverse Search is significantly faster, achieving a 4-5x speedup.

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.

  1. Robustness of Hashing: DNFApproxMC emerged 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.
  2. 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. DNFApproxMC remains consistent across these variations.
  3. 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.
Figure 6: Cactus plot showing the number of benchmarks solved within a given time limit. DNFApproxMC (green) dominates the field, solving all instances while others hit the timeout threshold.

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

Abstract

The problem of counting the number of solutions of a DNF formula, also called #DNF, is a fundamental problem in AI with wide-ranging applications. Owing to the intractability of the exact variant, efforts have focused on the design of approximate techniques. Consequently, several Fully Polynomial Randomized Approximation Schemes (FPRASs) based on Monte Carlo techniques have been proposed. Recently, it was discovered that hashing-based techniques too lend themselves to FPRASs for #DNF. Despite significant improvements, the complexity of the hashing-based FPRAS is still worse than that of the best Monte Carlo FPRAS by polylog factors. Two questions were left unanswered in previous works: Can the complexity of the hashing-based techniques be improved? How do these approaches compare empirically? In this paper, we first propose a new search procedure for the hashing-based FPRAS that removes the polylog factors from its time complexity. We then present the first empirical study of runtime behavior of different FPRASs for #DNF, which produces a nuanced picture. We observe that there is no single best algorithm for all formulas and that the algorithm with one of the worst time complexities solves the largest number of benchmarks.
BibTeX
@inproceedings{meel2019not,
  author = {Kuldeep S. Meel and Aditya A. Shrotri and Moshe Y. Vardi},
  title = {{Not All FPRASs are Equal: Demystifying FPRASs for DNF-Counting (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/865},
}
Figure