A Fine-Grained Complexity View on Propositional Abduction - Algorithms and Lower Bounds
Authors: Victor Lagerkvist, Mohamed Maizia, Johannes Schmidt
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for ΣP 2 as well as NP- and co NP-complete fragments... We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis. |
| Researcher Affiliation | Academia | 1 Department of Computer Science and Informatics, J onk oping University, J onk oping, Sweden 2 Department of Computer and Information Science, Link oping University, Link oping, Sweden EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 Algorithm A for P-ABD(Γ). |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the described methodology, nor does it provide any links to code repositories. |
| Open Datasets | No | The paper is theoretical, focusing on computational complexity, algorithms, and lower bounds for propositional abduction problems. It does not use or reference any specific datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets; therefore, no dataset splits are discussed or provided. |
| Hardware Specification | No | The paper is theoretical and focuses on complexity analysis and algorithm design. It does not describe any experimental hardware used to run experiments. |
| Software Dependencies | No | The paper is theoretical and does not detail any specific software dependencies or versions for implementing and running experiments. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithms and complexity analysis. It does not include an experimental setup with hyperparameters or system-level training settings. |