{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T04:12:58Z","timestamp":1730002378414,"version":"3.28.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>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 \u03a3\u1d3e, \u03a0\u1d3e, D\u1d3e, and \u0398\u1d3e, 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.<\/jats:p>","DOI":"10.24963\/kr.2024\/60","type":"proceedings-article","created":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T06:30:28Z","timestamp":1729924228000},"page":"642-653","source":"Crossref","is-referenced-by-count":0,"title":["Navigating and Querying Answer Sets: How Hard Is It Really and Why?"],"prefix":"10.24963","author":[{"given":"Dominik","family":"Rusovac","sequence":"first","affiliation":[{"name":"TU Dresden"}]},{"given":"Markus","family":"Hecher","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}]},{"given":"Martin","family":"Gebser","sequence":"additional","affiliation":[{"name":"University of Klagenfurt"}]},{"given":"Sarah Alice","family":"Gaggl","sequence":"additional","affiliation":[{"name":"TU Dresden"}]},{"given":"Johannes K.","family":"Fichte","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University"}]}],"member":"10584","event":{"name":"21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}","theme":"Artificial Intelligence","location":"Hanoi, Vietnam","acronym":"KR-2024","number":"21","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2024,11,1]]},"end":{"date-parts":[[2024,11,8]]}},"container-title":["Proceedings of the TwentyFirst International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T06:30:40Z","timestamp":1729924240000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2024\/60"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2024\/60","relation":{},"subject":[],"published":{"date-parts":[[2024,11]]}}}