The success of Answer Set Programming (ASP) stems from its highly expressive language, capable of modeling complex combinatorial problems, and from the availability of eficient solvers that make ASP practical in realworld scenarios. However, despite these strengths, the expressiveness of ASP is inherently limited to the second level of the Polynomial Hierarchy (PH). As a result, a wide range of problems that go beyond this complexity class cannot be modeled in ASP. To address this limitation, Answer Set Programming with Quantifiers (ASP(Q)) has been proposed. ASP(Q) extends the ASP language with the ability to quantify over answer sets, enabling a natural modeling of problems across the entire PH. In this tutorial, we explore the ASP(Q) formalism along the two dimensions that have driven the success of ASP: modeling capabilities and eficient solving. First, we will demonstrate how ASP(Q) allows for natural and intuitive modeling of several hard (optimization) problems of practical relevance. Then, we will turn our attention to the eficient evaluation of ASP(Q) programs. Specifically, we will introduce the PyQASP system, which compiles ASP(Q) programs into compact and optimized Quantified Boolean Formulae (QBF), allowing them to be evaluated efectively using well-established and mature QBF technologies. Through this tutorial, attendees will gain a comprehensive overview of the ASP(Q) formalism and how it can be applied to model and solve problems beyond NP across a variety of practical domains.
Declaration on The author(s) have not employed any Generative AI tools. CEUR