Complexity Results for Serial Decomposability

Abstract

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 requires that the set of solvable states is closed under the operators. It is PSPACE-complete to determine if a given finite state-variable problem is serially decomposable. In fact, every solvable instance of a PSPACE can be converted to a serially decomposable problem. Furthermore, given a bound on the size of the input, every in PSPACE can be transformed to a that is nearly serially-decomposable, i.e., the is serially decomposable except for closure of solvable states or a unique goal state.