Eiter, T., Fichte, J. K., Hecher, M., & Woltran, S. (2024). Epistemic Logic Programs: Non-Ground and Counting Complexity. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, {IJCAI} 2024, Jeju, South Korea, August 3-9,2024 (pp. 3333–3341). https://doi.org/10.24963/ijcai.2024/369
E192-02 - Forschungsbereich Databases and Artificial Intelligence E192-03 - Forschungsbereich Knowledge Based Systems E056-13 - Fachbereich LogiCS E056-23 - Fachbereich Innovative Combinations and Applications of AI and ML (iCAIML) E056-17 - Fachbereich Trustworthy Autonomous Cyber-Physical Systems
-
Erschienen in:
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, {IJCAI} 2024, Jeju, South Korea, August 3-9,2024
-
Datum (veröffentlicht):
9-Aug-2024
-
Veranstaltungsname:
Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)
Answer Set Programming (ASP) is a prominent problem-modeling and solving framework, whose solutions are called answer sets. Epistemic logic programs (ELP) extend ASP to reason about all or some answer sets. Solutions to an ELP can be seen as consequences over multiple collections of answer sets, known as world views. While the complexity of propositional programs is well studied, the non-ground case remains open. This paper establishes the complexity of non-ground ELPs. We provide a comprehensive picture for wellknown program fragments, which turns out to be complete for the class NEXPTIME with access to oracles up to Σ^P_2. In the quantitative setting, we establish complexity results for counting complexity beyond #EXP. To mitigate high complexity, we establish results in case of bounded predicate arity, reaching up to the fourth level of the polynomial hierarchy. Finally, we provide ETH-tight runtime results for the parameter treewidth, which has applications in quantitative reasoning, where we reason on (marginal) probabilities of epistemic literals.
