Introduction
Answer Set Programming (ASP) is a prominent declarative modeling paradigm used extensively in artificial intelligence for tasks such as planning, configuration, and bio-informatics. While modern ASP solvers like clingo are highly efficient at finding individual answer sets, many applications—particularly those involving probabilistic reasoning—require determining the total number of answer sets, a problem known as #ASP.
Counting answer sets is computationally demanding. For "normal" logic programs, the problem is #P-complete, while for "disjunctive" programs, it escalates to #·coNP-complete. Traditional approaches often rely on exhaustive enumeration or reduction to Boolean Satisfiability (SAT). However, enumeration is infeasible for large solution spaces, and reduction to SAT can cause an exponential blow-up in formula size due to the need for loop formulas.
Methodology: Hashing-Based Counting in ASP
ApproxASP addresses these challenges by adapting the hashing-based counting framework, originally developed for SAT (e.g., ApproxMC), directly into the ASP domain.
XOR Hashing and Theoretical Guarantees
The core mechanism involves adding random parity (XOR) constraints to the logic program. These constraints partition the solution space into smaller "cells." By counting the solutions within a single cell and scaling by the number of cells, the total count can be estimated with $(\epsilon, \delta)$ theoretical guarantees. The authors proved that these XOR constraints do not introduce spurious answer sets, preserving the logical integrity of the original program.
Native XOR Solving with GJE
A significant technical innovation in ApproxASP is the integration of a dedicated Gauss-Jordan Elimination (GJE) propagator within the clingo solver. Rather than treating XOR constraints as standard logical rules, the GJE propagator uses linear algebra to prune the search space efficiently. This "native" handling avoids the overhead of SAT reduction and allows the solver to detect conflicts and assignments that would otherwise be missed.
Experimental Evaluation
The performance of ApproxASP was evaluated against state-of-the-art counters, including ApproxMC, Ganak, and DynASP, using a diverse set of benchmarks.
Datasets
- Normal Programs: 1,500 instances derived from classic combinatorial problems like Vertex Cover and Dominating Set.
- Disjunctive Programs: 200 instances based on 2QBF problems, representing a higher level of complexity.
Performance Results
The results demonstrate that ApproxASP is uniquely capable of handling complex disjunctive programs. While SAT-based counters like Ganak and ApproxMC failed to solve any disjunctive instances due to the complexity of the reduction, ApproxASP successfully solved 185 out of 200.
On normal programs, ApproxASP proved to be highly competitive with ApproxMC, the leading SAT counter. As shown in the cactus plot below, both solvers exhibit similar scalability, significantly outperforming other specialized ASP counting tools.
Beyond scalability, ApproxASP demonstrated high empirical accuracy. Although the theoretical confidence ($\delta$) was set to 0.8, the observed average error across instances was only 0.037, far exceeding the theoretical bounds.
Conclusion and Future Work
ApproxASP represents the first scalable approximate counter for ASP with rigorous theoretical guarantees. By lifting hashing techniques from SAT and implementing native XOR propagation, it bypasses the limitations of SAT reduction and exhaustive enumeration.
Future research will focus on optimizing independent support selection for disjunctive programs and further refining the GJE propagator's integration with solver heuristics. These engineering improvements are expected to further enhance the tool's performance on increasingly complex real-world logic programs.
Summary updated