Epistemic Logic Programs: Non-Ground and Counting Complexity

• URL: http://arxiv.org/abs/2503.04731v1
• Date: Fri, 31 Jan 2025 20:08:52 GMT
• Title: Epistemic Logic Programs: Non-Ground and Counting Complexity
• Authors: Thomas Eiter, Johannes K. Fichte, Markus Hecher, Stefan Woltran,
• Abstract summary: Epistemic logic programs (ELP) extend ASP to reason about all or some answer sets.<n>This paper establishes the complexity of non-ground ELPs.
• Score: 32.575043686973224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \Sigma^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.

Related papers

• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning [92.76959707441954]
  We introduce ZebraLogic, a comprehensive evaluation framework for assessing LLM reasoning performance. ZebraLogic enables the generation of puzzles with controllable and quantifiable complexity. Our results reveal a significant decline in accuracy as problem complexity grows.
  arXiv  Detail & Related papers  (2025-02-03T06:44:49Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  We develop an algorithm for the complex task of computing the probability of a set of arguments being a complete extension. An experimental evaluation shows promise of our approach.
  arXiv  Detail & Related papers  (2024-07-06T12:08:38Z)
• Data Complexity in Expressive Description Logics With Path Expressions [7.832189413179361]
  We investigate the data complexity of the satisfiability problem for the expressive description logic ZOIQ (a.k.a. ALCHb Self reg OIQ) over quasi-forests. This completes the data complexity landscape for decidable fragments of ZOIQ, and reproves known results on decidable fragments of OWL2 (SR family)
  arXiv  Detail & Related papers  (2024-06-11T09:37:51Z)
• From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
  We show that languages allowing addition and marginalization yield NPPP, PSPACE, and NEXP-complete satisfiability problems, depending on the level of the PCH.<n>On the other hand, in the case of full languages, i.e. allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels.
  arXiv  Detail & Related papers  (2024-05-12T20:25:36Z)
• Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
  We deal with the classification of structural parameters for disjunctive ASP on the program's rule structure. We provide double-exponential lower bounds for the most prominent parameters in that range. Our results provide an in-depth hardness study, relying on a novel reduction from normal to disjunctive programs.
  arXiv  Detail & Related papers  (2024-02-05T21:51:36Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  Recent works leverage the capabilities of large language models (LMs) to perform complex question answering in a few-shot setting. We introduce Successive Prompting'', where we iteratively break down a complex task into a simple task, solve it, and then repeat the process until we get the final solution. Our best model (with successive prompting) achieves an improvement of 5% absolute F1 on a few-shot version of the DROP dataset.
  arXiv  Detail & Related papers  (2022-12-08T06:03:38Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs [22.39203220587435]
  We present a novel system that is capable of efficiently solving the underlying counting problems required to answer such quantitative reasoning problems. Our system exploits the graph-based measure treewidth and works by iteratively finding and refining (graph) abstractions of an ELP program. It turns out that our approach is competitive with existing systems that were introduced recently.
  arXiv  Detail & Related papers  (2021-08-06T09:46:34Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs) We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
  arXiv  Detail & Related papers  (2020-06-22T17:58:54Z)
• Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
  Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) We show that central problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds.
  arXiv  Detail & Related papers  (2020-01-13T13:16:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.