Introduction
Answer Set Programming (ASP) is a powerful declarative paradigm for solving complex combinatorial problems. However, a significant hurdle in its practical application is the "grounding bottleneck." Most modern solvers rely on a "ground-then-solve" approach, which involves expanding rules with variables into all possible ground instances. For many hard problems, this process leads to an exponential explosion in memory usage, often causing solvers to crash before they even begin the search for a solution.
This paper addresses the gap between the theoretical polynomial space complexity of certain ASP programs and the practical memory-intensive nature of current solvers. The authors introduce three novel evaluation methods and a prototype system, BPA (Bounded Predicate Arity), designed to operate within polynomial space limits.
Methodology: The BPA Framework
The core innovation lies in evaluating ASP programs without full grounding. The authors propose three methods tailored to different classes of programs:
- Method 1 (Normal Programs): Computes local answer sets by focusing on polynomially-sized subsets of the ground program.
- Method 2 (Head-Cycle-Free Programs): Employs a "supporting minimal guess" strategy, iterating over interpretations and verifying minimality in polynomial space.
- Method 3 (General Disjunctive Programs): Uses a two-step process to generate candidate models and verify them through subset enumeration.
The BPA system acts as a controller, delegating tasks to external engines. It uses the DLV solver for consistency checks and the XSB Prolog engine for top-down generation of relevant program subsets. This modular approach leverages the "Locality Lemma," which posits that an answer set of a program subset can be an answer set for the entire program if it satisfies all remaining rules.
Experimental Evaluation
The BPA prototype was tested against state-of-the-art solvers DLV and GrinGo/claspD across three benchmarks: 2QBF, ChainStratComp, and Clique.
Memory Efficiency
A key finding is the stability of BPA's memory usage. While traditional solvers exhibit exponential memory growth as problem instances scale, BPA maintains a nearly constant, low memory footprint.
In the 2QBF benchmark, for instance, BPA consistently operated within 22-26 MB, whereas competitors quickly exceeded the 2GB RAM limit.
Performance and Robustness
Contrary to the typical trade-off where space efficiency comes at the cost of time, BPA often outperformed traditional solvers on large instances. By avoiding the overhead of massive grounding, BPA remained responsive where other systems became paralyzed.
In the ChainStratComp benchmark, BPA's execution time scaled much more gracefully than its competitors. Furthermore, in the Clique benchmark, BPA successfully completed all 32 instances, while DLV and claspD failed on nearly half due to memory exhaustion.
Conclusion and Future Directions
The BPA framework demonstrates that space-efficient ASP evaluation is not only theoretically possible but practically advantageous for large-scale problems. While the current prototype faces some implementation hurdles, such as memory leaks in external components and a lack of support for advanced features like aggregates, it proves that the grounding bottleneck can be overcome. Future work will focus on integrating these methods directly into solvers and optimizing subprogram pruning to further enhance performance.
Summary updated