KR2024Proceedings of the 21st International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning

Hanoi, Vietnam. November 2-8, 2024.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-05-8

Sponsored by
Published by

Copyright © 2024 International Joint Conferences on Artificial Intelligence Organization

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

  1. Dominik Rusovac(TU Dresden)
  2. Markus Hecher(Massachusetts Institute of Technology)
  3. Martin Gebser(University of Klagenfurt)
  4. Sarah Alice Gaggl(TU Dresden)
  5. Johannes K. Fichte(Linköping University)

Keywords

  1. Computational aspects of knowledge representation-General
  2. Knowledge compilation, automated reasoning, satisfiability and model counting-General
  3. Logic programming, answer set programming-General

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 Σᴾ, Πᴾ, Dᴾ, and Θᴾ, 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.