Computational Complexity of Computing Symmetries in Finite-Domain Planning
Authors: Alexander Shleyfman, Peter Jonsson
JAIR 2021 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We explain this phenomenon by showing that Struct Sym is GI-complete, i.e., the graph isomorphism problem is polynomial-time equivalent to it and, consequently, solvable in quasi-polynomial time. This implies that it is solvable substantially faster than most computationally hard problems encountered in AI. We accompany this result by identifying natural restrictions of the planning task and its causal graph that ensure that Struct Sym can be solved in polynomial time. Given that the Struct Sym problem is GI-complete and thus solvable quite efficiently, it is interesting to analyse if other symmetries (than those that are encompassed by the Struct Sym problem) can be computed and/or analysed efficiently, too. To this end, we present a highly negative result: checking whether there exists an automorphism of the state transition graph that maps one state s into another state t is a PSPACE-hard problem and, consequently, at least as hard as the planning problem itself. |
| Researcher Affiliation | Academia | Alexander Shleyfman EMAIL Department of Mechanical and Industrial Engineering University of Toronto Canada Peter Jonsson EMAIL Department of Computer and Informaton Science Link oping University Sweden |
| Pseudocode | No | The paper provides mathematical definitions, theorems, lemmas, and proofs for theoretical complexity analysis. It does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statements about releasing source code for the methodology described. It focuses on theoretical complexity analysis rather than empirical implementation. |
| Open Datasets | No | The paper focuses on theoretical computational complexity within finite-domain planning and does not describe or utilize any specific datasets for experimental evaluation. Therefore, there is no mention of publicly available datasets or access information. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments with datasets, thus no information about training/test/validation dataset splits is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity analysis. It does not describe any experiments that would require specific hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is a theoretical work focusing on computational complexity. It refers to established algorithms and methods (e.g., Luks (1982), Babai (2015)) in a theoretical context but does not mention specific software dependencies or versions for its own implementation or experiments. |
| Experiment Setup | No | The paper is theoretical, presenting proofs and complexity analysis, and does not include any experimental setup details such as hyperparameters or system-level training settings. |