Epistemic Logic Programs: Non-Ground and Counting Complexity
Authors: Thomas Eiter, Johannes K. Fichte, Markus Hecher, Stefan Woltran
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the precise computational complexity of qualitative and quantitative decision and reasoning problems for non-ground ELPs. Our contributions are detailed below. In addition, Table 1 surveys details and illustrates relations to existing results. 1. We provide a comprehensive picture of the non-ground ELP landscape, including common program fragments. We mitigate complexity by showing how complexity results drop if predicate arities are bounded a typical assumption for solving. 2. We establish detailed complexity results for counting problems, which enables more fine-grained reasoning. To this end, we lift counting complexity notions to the weak-exponential hierarchy. 3. We analyze the impact of structural restrictions in form of bounded treewidth. |
| Researcher Affiliation | Academia | Thomas Eiter1 , Johannes K. Fichte2 , Markus Hecher3 , Stefan Woltran1 1Institute of Logic and Computation, TU Wien 2Department of Computer and Information Science (IDA), Link oping University 3Computer Science & Artificial Intelligence Laboratory, Massachusetts Institute of Technology |
| Pseudocode | No | The paper provides formalized constructions of logic programs (e.g., P1, P2, P3, P4, P5 in Section 3.1) and proof sketches, but it does not contain any clearly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not provide an explicit statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with training, validation, or test data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments requiring specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not detail specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experimental setups or hyperparameters. |