Navigating and Querying Answer Sets: How Hard Is It Really and Why?

Research output: Contribution to conferencesPaperContributedpeer-review

Contributors

Abstract

Answer set programming is a popular declarative paradigm with countless applications for modeling and solving combinatorial problems. We can view a program as a knowledge database compactly representing conditions for solutions. Often we are interested in reasoning about solutions of filtering answer sets. At the heart of these questions is brave and cautious reasoning. For browsing answer sets, we combine both as restricting atoms of answer sets is only meaningful for atoms called facets that belong to some (brave) but not to all answer sets (cautious). Surprisingly, the precise computational complexity of facet problems remained widely open so far. In this paper, we study the complexity of answer set facets. We establish tight results for reasoning with facets, deciding upper and lower bounds as well as the exact number of facets, and comparing facets. Facet reasoning seems to be a natural problem formalism, residing in complexity families ΣP, ΠP, DP, and ΘP, up to the third level. Moreover, our study considers quantitative importance questions on facets and generalizing from facets to conjunctions, disjunctions, and arbitrary queries. We complete our results by an experimental evaluation.

Details

Original languageEnglish
Pages642–653
Number of pages12
Publication statusPublished - 2024
Peer-reviewedYes

Conference

Title21st International Conference on Principles of Knowledge Representation and Reasoning
Abbreviated titleKR 2024
Conference number21
Duration2 - 8 November 2024
Website
Degree of recognitionInternational event
LocationPullman Hotel
CityHanoi
CountryViet Nam

External IDs

ORCID /0000-0003-2425-6089/work/173986260
unpaywall 10.24963/kr.2024/60
Mendeley 91e39949-05ba-3498-80c7-764fc1c92aa9