Complexity Results for Serial Decomposability

Tom BylanderAAAI 1992

Introduction

In the field of automated planning and heuristic search, the efficiency of a solver often depends on the structural properties of the state space. One such property, serial decomposability, was popularized by Richard Korf in the mid-1980s through the Macro Problem Solver (MPS). MPS demonstrated that if a problem can be broken down such that state variables are solved sequentially without disturbing previously fixed variables—much like solving a Rubik's Cube layer by layer—it can be solved efficiently using a library of "macro-operators."

While MPS provided a powerful framework for specific puzzles, the theoretical complexity of identifying whether a given problem is serially decomposable remained an open question. In this paper, Tom Bylander investigates the computational limits of detecting this structure, proving that the task is significantly more difficult than previously assumed.

Defining Serial Decomposability

Bylander formalizes the property into two distinct levels to analyze their respective complexities:

  1. Operator Decomposability: An operator is serially decomposable with respect to a specific variable ordering if the effect of the operator on variable $i$ depends only on the values of variables $1$ through $i$.
  2. Problem Decomposability: A problem is considered fully serially decomposable if its operators satisfy the above condition and the problem exhibits operator closure. Closure ensures that if a state is solvable, applying any operator from the set will result in another solvable state, preventing the solver from entering "dead ends."

Complexity Analysis

The core of Bylander’s work involves mapping these definitions to known complexity classes using formal reductions, such as mapping Turing Machine configurations to state-variable problems.

Operator Complexity

The study finds that determining if a specific operator is not serially decomposable for a given variable ordering is coNP-complete. Interestingly, even if the variable ordering is unknown, the complexity of determining operator decomposability remains coNP-complete. This suggests that even at the local level of individual actions, verifying the "serial" property is computationally taxing.

Problem Complexity (SDSAT)

The most significant result concerns the detection of serial decomposability at the problem level, referred to as SDSAT. Bylander proves that SDSAT is PSPACE-complete. This places the detection of the property in the same complexity class as the most difficult problems solvable within polynomial space, suggesting that finding this structural "shortcut" is often as hard as solving the original problem itself.

The "Closure" Trap and Universality

A key insight from the paper is that the difficulty of SDSAT does not stem solely from the serial nature of the operators. Instead, the primary bottleneck is operator closure. Proving that an action will not lead to an unsolvable state is inherently difficult because it requires verifying the reachability of the goal state across the state space.

Bylander further demonstrates a "universality" paradox: any problem in PSPACE can be transformed into a serially decomposable one in polynomial time. However, this transformation is often a mathematical artifact. To achieve serial decomposability, one must typically sacrifice either the unique goal state or the operator closure property. Without these, the guarantees provided by Korf’s MPS algorithm vanish, rendering the "decomposable" version of the problem no easier to solve than the original.

The PSPACE-completeness of SDSAT has profound implications for the Macro Problem Solver and similar heuristic methods. It suggests that the exponential running time observed in MPS is not an algorithmic flaw but a reflection of the underlying complexity of the problem. If a polynomial-time algorithm existed to detect serial decomposability and find the corresponding macros, it would imply that P = PSPACE—a major and unlikely breakthrough in computer science.

Conclusion

Bylander’s results provide a sobering look at the "shortcuts" used in AI search. While serial decomposability is a powerful property when known, the act of discovering it is as hard as solving the problem itself. The paper concludes that future research should focus on identifying specific classes of problems where this property can be detected efficiently or finding "natural" representations of common AI domains that satisfy these properties without resorting to artificial mathematical transformations.

Summary updated

BibTeX
@inproceedings{bylander1992complexity,
  author = {Tom Bylander},
  title = {{Complexity Results for Serial Decomposability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure