Navigating and Querying Answer Sets: How Hard Is It Really and Why?
Research output: Contribution to conferences › Paper › Contributed › peer-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 language | English |
|---|---|
| Pages | 642–653 |
| Number of pages | 12 |
| Publication status | Published - 2024 |
| Peer-reviewed | Yes |
Conference
| Title | 21st International Conference on Principles of Knowledge Representation and Reasoning |
|---|---|
| Abbreviated title | KR 2024 |
| Conference number | 21 |
| Duration | 2 - 8 November 2024 |
| Website | |
| Degree of recognition | International event |
| Location | Pullman Hotel |
| City | Hanoi |
| Country | Viet Nam |
External IDs
| ORCID | /0000-0003-2425-6089/work/173986260 |
|---|---|
| unpaywall | 10.24963/kr.2024/60 |
| Mendeley | 91e39949-05ba-3498-80c7-764fc1c92aa9 |