

![0_image_0.png](0_image_0.png)

Figure 1 displays the partial order on propositional planning formalisms defined in this way. In the sequel we say that X **is a specialization** of Y, written X v Y, iff X is identical to Y or below Y in the diagram depicting the partial order.

Comparing this set of planning formalisms with the one B¨ackstr¨om (1995) analyzed,5one notices that despite small differences in the presentation of the planning formalisms:
 S is the same as *common propositional strips* (CPS), S is the same as *propositional strips with negative goals* (PSN), and

 SLI is the same as *ground Tweak* (GT).

## 2.3 The Computational Complexity Of Planning In The S-Family

While one would expect that planning in S is much easier than planning in SBIC , it turns out that this is not the case, provided one takes a computational complexity perspective.

In analyzing the computational complexity of planning in different formalisms, we consider, as usual, the problem of deciding whether there *exists a plan* for a given instance—the plan existence problem (PLANEX). We will use a prefix referring to the planning formalism if we consider the existence problem in a particular planning formalism.

Theorem 3 X -PLANEX is PSPACE-complete for all X *with* S v X v SBIC .