Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Epistemic Logic Programs: Non-Ground and Counting Complexity
Authors: Thomas Eiter, Johannes K. Fichte, Markus Hecher, Stefan Woltran
IJCAI 2024 | Venue PDF | 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. |