Epistemic Logic Programs: Non-Ground and Counting Complexity
Not on the map. Why?
Abstract (arXiv)
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 well-known program fragments, which turns out to be complete for the class NEXPTIME with access to oracles up to SigmaP2. 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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 12 of its 69 references that are in the map. First posted on arXiv 31 Jan 2025.
Builds on
12 of 69 references.
References · 12
- 2020Advancing Lazy-Grounding ASP Solving Techniques -- Restarts, Phase Saving, Heuristics, and Morecited by 10
- 2021Rushing and Strolling among Answer Sets -- Navigation Made Easycited by 9
- 2022Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?cited by 8
- 2020selp: A Single-Shot Epistemic Logic Program Solvercited by 7
- 2020eclingo: A solver for Epistemic Logic Programscited by 7
- 2017Constraint Solving via Fractional Edge Coverscited by 5
- 2020Structural Decompositions of Epistemic Logic Programscited by 5
- 2021Thirty years of Epistemic Specificationscited by 4
- 2015Dual-normal Logic Programs - the Forgotten Classcited by 3
- 2021Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programscited by 3
- 2017Default Logic and Bounded Treewidthcited by 2
- 2019Epistemic Logic Programs: A Different World Viewcited by 2
Built on by
Citing papers per year: 2025: 1.
1 paper.