On the Parameterized Complexity of Belief Revision
Authors: Andreas Pfandler, Stefan Rümmele, Johannes Peter Wallner, Stefan Woltran
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Parameterized complexity is a well recognized vehicle for understanding the multitude of complexity AI problems typically exhibit. However, the prominent problem of belief revision has not undergone a systematic investigation in this direction yet. This is somewhat surprising, since by its very nature of involving a knowledge base and a revision formula, this problem provides a perfect playground for investigating novel parameters. Among our results on the parameterized complexity of revision is thus a versatile fpt algorithm which is based on the parameter of the number of atoms shared by the knowledge base and the revision formula. Towards identifying the frontier between parameterized tractability and intractability, we also give hardness results for classes such as co-W[1], para-ΘP 2, and FPTNP[f(k)]. |
| Researcher Affiliation | Academia | 1Vienna University of Technology, Austria 2University of Siegen, Germany |
| Pseudocode | Yes | Algorithm 1: Fpt-algorithm of Theorem 7 |
| Open Source Code | No | The paper is theoretical and focuses on complexity analysis and algorithm design. It does not mention providing any open-source code for its own methodology. |
| Open Datasets | No | The paper is theoretical and does not involve experiments with datasets. No datasets are mentioned. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments with datasets. No dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not report on any computational experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not report on any computational experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training settings. |