Complexity Results for Serial Decomposability

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.

Authors

• Tom Bylander

Keywords

No keywords are indexed for this paper.