Abstract
Answer Set Programming (ASP) has long struggled with the efficient handling of non-convex aggregates, which often push computational complexity to the second level of the polynomial hierarchy ($\Sigma_{2}^{P}$). This paper, originally presented at IJCAI-16, bridges this gap by introducing a polynomial-time, faithful, and modular translation that converts complex non-convex aggregates into simpler monotone ones. By leveraging disjunction in rule heads and a specialized saturation technique, the authors enable modern ASP solvers to tackle high-complexity combinatorial problems that were previously intractable. The approach, integrated into the gringo grounder, significantly outperforms state-of-the-art SMT solvers on benchmark tasks.
Introduction
In Answer Set Programming, "aggregates" are essential constructs used to describe properties of sets, such as the sum of weights or the count of selected items. Most ASP implementations are highly optimized for monotone aggregates, where the truth value of a statement (e.g., SUM > 10) remains true as more elements are added to the set.
However, many real-world problems require non-convex aggregates, such as "the sum must not equal $X$" (SUM != X). These are significantly more difficult to solve because their truth value can fluctuate as the set grows. Before this research, non-convex aggregates in certain programs pushed complexity to $\Sigma_{2}^{P}$, while standard solvers were primarily designed for NP-level problems. Previous attempts to rewrite these aggregates often failed to preserve the "stable model" semantics—the mathematical foundation of ASP—leading to incorrect or incomplete results.
Methodology
The authors propose a translation function that is polynomial, faithful, and modular. The core innovation lies in using disjunction in rule heads to bridge the complexity gap between NP and $\Sigma_{2}^{P}$.
Mapping to Sums
The translation first demonstrates that various aggregate types, including COUNT, MAX, and MIN, can be logically equated to SUM aggregates. This unification allows the solver to apply a standardized logic to different aggregate structures.
Handling Non-Convexity via Saturation
To handle non-convex operators like !=, the authors split the aggregate into two cases: > and <. However, a simple "either-or" rule is insufficient to maintain stable model semantics. The researchers introduced a saturation mechanism using auxiliary atoms. This ensures that the solver correctly explores all possible assignments in the program reduct (the simplified version of the program used to verify solutions), preventing the solver from incorrectly discarding valid stable models.
Implementation
This logic was integrated into gringo 4.5, the standard grounder for the Potassco ASP suite. This integration allows the solver to handle non-convexity during the grounding phase, translating complex constraints into a format that the solver clasp can process efficiently.
Experimental Evaluation
The researchers evaluated their approach using the Generalized Subset Sum problem. Given two vectors of integers and a target value $b$, the task is to decide if there exists a selection $x$ such that for all possible selections $y$, the combined sum is not equal to $b$. This is a classic $\Sigma_{2}^{P}$-complete problem, serving as a rigorous stress test for the new translation.
The ASP-based approach (gringo + clasp) was compared against the high-performance SMT (Satisfiability Modulo Theories) solver Z3.
Key Results
- Performance: Out of 46 hard instances of the Generalized Subset Sum problem, the ASP solver solved 38 instances within a 900-second timeout. In contrast, Z3 managed to solve only 14 instances.
- Complexity: The translation proved to be polynomial in both time and space, ensuring that program size does not explode during the grounding phase.
- Faithfulness: The authors proved that their translation is "faithful," meaning it identifies exactly the same stable models as the original complex program, but in a format the solver can actually execute.
Conclusion and Future Work
This research identifies that the primary failure of previous solvers was the lack of a mechanism to handle the interaction between negative literals in aggregates and the stable model reduct. By proving that disjunction is necessary for this translation (unless the polynomial hierarchy collapses), the authors have provided a definitive path forward for high-complexity ASP solving.
Future work remains in optimizing the translation for heavily recursive programs and extending these optimized structures to other non-convex aggregates without requiring an intermediate conversion to sums. Testing the approach on broader industrial configuration and scheduling problems will further validate its real-world utility.
Summary updated