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

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.