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

arXiv: https://arxiv.org/abs/2605.27338 · HTML: https://mlsanity.com/paper/2605.27338/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 36 references that are in the map.
- First posted on arXiv 26 May 2026.

## Builds on (most cited first, 6 of 6)

- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Planning with Incomplete Information in Quantified Answer Set Programming](https://mlsanity.com/paper/2108.06405/) (2021)
- [Beyond NP: Quantifying over Answer Sets](https://mlsanity.com/paper/1907.09559/) (2019)
- [Stable-Unstable Semantics: Beyond NP with Normal Logic Programs](https://mlsanity.com/paper/1608.01835/) (2016)
- [An efficient solver for ASP(Q)](https://mlsanity.com/paper/2305.10021/) (2023)
- [Quantifying over Optimum Answer Sets](https://mlsanity.com/paper/2408.07697/) (2024)

## Abstract (arXiv)

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.