if we allow linear growth of the resulting plans. Nevertheless, there might still be a chance for compilation schemes preserving plan size polynomially. Having shown that SBIC and SBI cannot be compiled to the other formalisms even if the plan can grow polynomially, we may still be able to find compilation schemes preserving plan size polynomially for the SBIC /SBI pair and for the remaining formalisms.

A preview of the results of this section is given in Figure 7. As it can be seen, we are able

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

Figure 7: Equivalence classes of planning formalisms created by polynomial-time compilation schemes preserving plan size polynomially. Compilation schemes constructed in this section are indicated by dashed lines
to establish compilation schemes preserving plan size polynomially for all pairs of formalisms for which we have not proved the impossibility of such compilation schemes.

## 6.1 Compiling Conditional Effects Away For Partial State Specifications

The first compilation scheme we will develop is one from SBIC to SBI . As before, we assume that the conditional effects have only singleton effect sets. Further, since we can use arbitrary boolean formulae in the effect conditions in SBIC , we assume that there is only one rule for each effect literal.

Using a simple polynomial transformation, arbitrary sets of operators can be brought into this form.

This simplifies checking the condition A S; *post* o)) P S; *post* o)) considerably, because now only one rule can activate a particular literal.