2-ASP(Q) programs with weak constraints: Complexity and efficient implementation

Problem
This paper addresses the gap in the computational complexity and practical implementation of 2-ASP(Q) programs with weak constraints, a fragment of Answer Set Programming (ASP) that incorporates quantifiers over answer sets. The authors highlight that while ASP(Q) has been studied, the specific case of 2-ASP(Q)^w has not been thoroughly characterized in terms of complexity or efficient computation strategies. This work is presented as a preprint and has not undergone peer review.

Method
The authors provide a complete complexity characterization for 2-ASP(Q)^w, detailing the computational tasks associated with this class of programs. They establish tight completeness results and analyze nontrivial cases that were previously unexplored. On the practical side, they introduce novel strategies for computing optimal quantified answer sets within the Casper system. These strategies leverage a Counterexample-Guided Abstraction Refinement (CEGAR) technique specifically adapted for ASP(Q). The implementation details include the use of weak constraints to enhance the expressiveness and efficiency of the solution process.

Results
The experimental evaluation demonstrates that the proposed CEGAR-based strategies significantly improve the performance of the Casper system on challenging benchmarks across various application domains. The authors report that their methods outperform existing baselines, although specific numerical results and comparisons to named baselines are not detailed in the abstract. The effectiveness of the techniques is underscored by their ability to handle optimization problems up to the complexity class Δ_3^P, indicating a substantial advancement in the practical applicability of ASP(Q).

Limitations
The authors acknowledge that their work is limited to the specific class of 2-ASP(Q)^w programs and may not generalize to other forms of ASP or more complex quantifier structures. Additionally, while the CEGAR technique shows promise, its scalability and performance on larger or more complex instances remain to be fully evaluated. The paper does not address potential limitations related to the computational resources required for implementing the proposed strategies, nor does it discuss the implications of the complexity results on real-world applications.

Why it matters
This research has significant implications for the field of knowledge representation and reasoning, particularly in optimization problems that can be modeled using ASP. By providing a comprehensive complexity analysis and practical implementation strategies, the work enhances the understanding of 2-ASP(Q)^w and opens avenues for further exploration in automated reasoning systems. The findings could lead to more efficient algorithms for solving complex decision problems, thereby impacting various domains such as artificial intelligence, operations research, and beyond.

Authors: Andrea Cuteri, Giuseppe Mazzotta, Francesco Ricca
Source: arXiv:2605.27338
URL: https://arxiv.org/abs/2605.27338v1