Treewidth-Aware Complexity for Evaluating Epistemic Logic Programs
Authors: Jorge Fandinno, Markus Hecher
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present complexity results for the evaluation of key ELP fragments for treewidth, which are exponentially better than known results for full ELPs. Unfortunately, we prove that obtained runtimes can not be significantly improved, assuming the exponential time hypothesis. Our approach defines treewidth-aware reductions between quantified Boolean formulas and ELPs. We also establish that the completion of a program, as used in modern solvers, can be turned treewidth-aware, thereby linearly preserving treewidth. |
| Researcher Affiliation | Academia | 1University of Nebraska Omaha, NE, USA 2Massachusetts Institute of Technology, MA, USA |
| Pseudocode | No | The paper describes methods and transformations using mathematical formulas and propositional logic, but it does not include any explicitly labeled pseudocode blocks or algorithms. |
| Open Source Code | No | The paper discusses concepts related to "modern solvers" and "ASP solvers" but does not provide a link or explicit statement about releasing source code for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training on datasets. Therefore, no information about publicly available training datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Therefore, no information about validation splits is provided. |
| Hardware Specification | No | The paper focuses on theoretical complexity analysis and does not describe any empirical experiments. As such, no hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | The paper refers to general concepts like "ASP solvers" but does not list specific software dependencies with version numbers that would be required to reproduce any empirical work. |
| Experiment Setup | No | The paper is theoretical, analyzing complexity and proposing reductions. It does not describe an experimental setup with hyperparameters or system-level training settings. |