2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
2026-05-26 • Artificial Intelligence
Artificial IntelligenceComputational ComplexityComputation and LanguageLogic in Computer Science
AI summaryⓘ
The authors study a specific type of logic programming called ASP(Q), which adds quantifiers to Answer Set Programming. They focus on a version with two quantifiers and weak constraints, called 2-ASP(Q)^w, which can express complex optimization problems. The paper provides a full analysis of how hard it is to solve these problems and introduces new methods to find solutions efficiently using a technique called CEGAR. Their experiments with difficult examples show that their methods work well in practice.
Answer Set ProgrammingQuantifiersWeak Constraints2-ASP(Q)^wDelta_3^PComputational ComplexityOptimization ProblemsCounterexample-Guided Abstraction Refinement (CEGAR)Casper system
Authors
Andrea Cuteri, Giuseppe Mazzotta, Francesco Ricca
Abstract
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.