2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
For researchers and practitioners in answer set programming, this work advances the understanding and practical solving of quantified ASP with optimization, though the gains are incremental over prior ASP(Q) work.
This paper provides a complete complexity characterization of 2-ASP(Q)^w programs with weak constraints, showing they capture optimization problems up to Δ₃ᴾ, and introduces CEGAR-based strategies in the Casper system that improve performance on hard benchmarks.
ASP(Q) extends Answer Set Programming (ASP) with Quantifiers over answer sets. In this paper we focus on the class of ASP(Q) programs with two quantifiers and weak constraints, denoted as 2-ASP(Q)^w. 2-ASP(Q)^w is a practically relevant fragment of ASP(Q) that is expressive enough to capture optimization problems up to the class Delta_3^P. On the theoretical side, we provide a complete complexity characterization of the main computational tasks for 2-ASP(Q)^w programs, including tight completeness results and the analysis of nontrivial cases that have not been addressed in previous works. On the practical side, we introduce novel strategies for computing (optimal) quantified answer sets in the Casper system, that rely on a Counterexample-Guided Abstraction Refinement (CEGAR) technique tailored to ASP(Q). An experimental evaluation on hard benchmarks from different application domains shows that the proposed techniques are effective in practice.