Fixed-Parameter Tractable Reductions to SAT for Planning
Authors: Ronald de Haan, Martin Kronegger, Andreas Pfandler
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we use the framework of parameterized complexity theory to obtain a more fine-grained complexity analysis of natural planning problems beyond NP. With this analysis we are able to point out several variants of planning where the structure in the input makes encodings into SAT feasible. We complement these positive results with some hardness results and a new machine characterization for the intractability class k-W[P]. |
| Researcher Affiliation | Academia | 1Vienna University of Technology, Austria 2University of Siegen, Germany |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. It focuses on theoretical proofs and complexity analysis. |
| Open Source Code | No | The paper does not mention or provide any links to open-source code for the described methodology. The paper is theoretical in nature. |
| Open Datasets | No | The paper is theoretical and does not involve experiments with datasets, so no training data is mentioned or made available. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental validation or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |