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].
On the Parameterized Complexity of Belief Revision
Authors: Andreas Pfandler, Stefan Rรผmmele, Johannes Peter Wallner, Stefan Woltran
IJCAI 2015 | Venue PDF | 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. |