Complexity Results for Serial Decomposability

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Volume

Representation and Reasoning

Representation and Reasoning: Temporal

Korf (1985) presents a method for learning macro-operators and shows that the method is applicable to serially decomposable problems. In this paper I analyze the computational complexity of serial decomposability. Assuming that operators take polynomial time, it is NP-complete to determine if an operator (or set of operators) is not serially decomposable, whether or not an ordering of state variables is given. In addition to serial decomposability of operators, a serially decomposable probIem requires that the set of solvable states is closed under the operators. It is PSPACEcomplete to determine if a given "finite state-variable problem" is serially decomposable. In fact, every solvable instance of a PSPACE problem can be converted to a serially decomposable problem. Furthermore, given a bound on the size of the input, every problem in PSPACE can be transformed to a probIem that is nearly serially-decomposable, i.e., the problem is serially decomposable except for closure of solvable states or a unique goal state.