Abstract
Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. In this paper, we study the complexity of planning in the class $C_n$ of planning problems, characterized by unary operators and directed path causal graphs. Although this is one of the simplest forms of causal graphs a planning problem can have, we show that planning is intractable for $C_n$ (unless P = NP), even if the domains of state variables have bounded size. In particular, we show that plan existence for $C_n^k$ is NP-hard for $k \ge 5$ by reduction from CNFSAT. Here, $k$ denotes the upper bound on the size of the state variable domains. Our result reduces the complexity gap for the class $C_n^k$ to cases $k=3$ and $k=4$ only, since $C_n^2$ is known to be tractable.
The Search for the Tractability Boundary
In automated planning, researchers strive to identify the "tractability boundary"—the precise point where a problem transitions from being efficiently solvable (in polynomial time) to being computationally intractable (NP-hard). A common way to categorize these problems is by their causal graph, which represents the dependencies between different state variables.
A chain causal graph ($C_n$) represents the simplest possible acyclic dependency structure. In this model, each variable depends only on its immediate predecessor, forming a single directed path.
Previous research established that planning is tractable when variables are binary (domain size $k=2$). Conversely, the problem is known to be hard when the domain size grows with the number of variables ($k=O(n)$). However, the complexity of problems with small, fixed domain sizes—specifically $k=3, 4, 5$—remained a significant open question. This paper addresses this gap by proving that even a domain size of 5 is sufficient to trigger NP-hardness.
Methodology: Reduction from CNF-SAT
The authors establish NP-hardness through a formal reduction from the Boolean Satisfiability problem (CNF-SAT). They demonstrate that any SAT instance can be encoded as a planning problem featuring a chain causal graph and a maximum domain size of 5. The core of this reduction involves treating the chain of variables as a sequence of finite-state automata that perform three distinct functions:
- Message Generation: The initial segment of the chain generates a "message" that represents a specific variable assignment for the SAT formula.
- Clause Verification: The middle segment consists of variables acting as checkers. Each variable in this stage verifies whether the current assignment satisfies a specific clause in the SAT formula.
- Propagation: The final segment ensures that a "satisfied" signal is successfully passed to the end of the chain to reach the goal state.
While the authors initially present a more intuitive reduction requiring a domain size of $k=11$, they introduce a sophisticated "backward propagation" technique to compress the state space. This technique allows variables to check bits of the assignment in reverse order, enabling state reuse and bringing the required domain size down to $k=5$.
Key Insights and Results
The primary finding is that structural simplicity is deceptive. A linear chain of dependencies might seem easy to solve, but the paper proves that this minimal structure can compute complex logic if variables possess enough internal states. The behavior of these variables is defined using Domain Transition Graphs (DTGs), which map how a variable's value changes based on the state of its predecessor. By carefully engineering these transitions, the authors force the planner to effectively "guess" a satisfying assignment for a SAT formula.
Refining the Complexity Gap
This work significantly narrows the known complexity gap for chain causal graphs:
- $k=2$: Tractable (P)
- $k=3, 4$: Unknown (The remaining gap)
- $k \ge 5$: Intractable (NP-hard)
Furthermore, the authors note that for $k \ge 3$, plans can be exponentially long. This implies that even if we could determine plan existence quickly, the plans themselves might be too large to represent in polynomial time without compression.
Conclusion and Future Work
By proving that $k=5$ is NP-hard, the authors have pushed the boundary of intractability closer to the simplest possible cases. Future research will likely target the remaining cases of $k=3$ and $k=4$. The case of $k=3$ is particularly interesting, as it is the minimum domain size where exponential plan lengths are possible, yet it may still permit polynomial-time algorithms for determining plan existence.
Summary updated