Beyond NP: Quantifying over Answer Sets

Giovanni Amendola, Francesco Ricca, Miroslaw Truszczynski

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Answer Set Programming (ASP) is a logic programming paradigm featuring a purely declarative language with comparatively high modeling capabilities. Indeed, ASP can model problems in NP in a compact and elegant way. However, modeling problems beyond NP with ASP is known to be complicated, on the one hand, and limited to problems in on the other. Inspired by the way Quantified Boolean Formulas extend SAT formulas to model problems beyond NP, we propose an extension of ASP that introduces quantifiers over stable models of programs. We name the new language ASP with Quantifiers (ASP(Q)). In the paper we identify computational properties of ASP(Q); we highlight its modeling capabilities by reporting natural encodings of several complex problems with applications in artificial intelligence and number theory; and we compare ASP(Q) with related languages. Arguably, ASP(Q) allows one to model problems in the Polynomial Hierarchy in a direct way, providing an elegant expansion of ASP beyond the class NP.

Original languageEnglish
Pages (from-to)705-721
Number of pages17
JournalTheory and Practice of Logic Programming
Volume19
Issue number5-6
DOIs
StatePublished - Sep 1 2019

Bibliographical note

Funding Information:
The work of the third author has been partially supported by the NSF grant IIS-1707371. This work has been partially supported by MIUR under PRIN 2017 project n. 2017M9C25L 001 (CUP H24I17000080001).

Publisher Copyright:
© 2019 Cambridge University Press.

Keywords

  • ASP
  • Polynomial Hierarchy
  • Quantified Logics

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Beyond NP: Quantifying over Answer Sets'. Together they form a unique fingerprint.

Cite this