Conversely, if S , then there does not exist any plan that transforms

```
                     R S fi(); o
                              pre
                              i
                              
into a legal state specification that contains c and poi
                              
                              .
  Using induction on the plan length, it follows from the arguments above that there exists a plan
 for iff there exists a plan for F () and for every such plan we have jj jj  jj jj - (3
2m , with m being the maximum number of conditional effects in operators of O. Hence f is a
polynomial-time compilation scheme preserving plan size polynomially.

```

An immediate consequence of this theorem is that SBIC and SBI form an equivalence class with respect to compilability preserving plan size polynomially. Corollary 21 SBIC and SBI *are polynomial-time compilable to each other preserving plan size* polynomially.

Further, we know from Corollary 15 that this class cannot become larger.

As in the case of compiling SLIC to SLC , however, the result depends on the semantics chosen for executing conditional effects over partial state specifications. If we use the alternative semantics where the resulting state specification is legal when the application of all state-transformation functions leads to a theory that can be represented as a set of literals, it seems likely that there exists another scheme that preserves plan size polynomially. However, if we use the alternative semantics that deletes all the literals in P S; *post* o))  A S; *post* o)) if P S; *post* o is consistent, then it appears to be very unlikely that we are able to identify a compilation scheme that preserves plan size polynomially.

## 6.2 Compiling Conditional Effects Away For Complete State Specifications

The next compilation scheme compiles SBC to S and SLC to S . Since we deal with complete state specification, we do not have to take care of the condition A S; *post* o)) P S; *post* o)), which is always true for complete states. This makes the compilation scheme somewhat simpler. Since S does not allow for general boolean formulae, the scheme becomes a little bit more difficult. In general, however, the compilation scheme we will specify is very similar to the one given in the proof of Theorem 20.

Theorem 22 SBC can be compiled to S and SLC can be compiled to S *in polynomial time preserving plan size polynomially.*
Proof. As in the proof of Theorem 20, we assume that h ; Oi is the (SBC or SLC ) source domain structure. Further, we assume that all operators have the form

```
oi hpre oi ;
                  i;1 ) l
                          i;1; : : : ;
                                    i;mi ) li;mi gi;

```

with l i;j and i;j   if is a SBC structure or i;j  if is a SLC structure. This means that we do not assume the effects to be unique for each conditional effect.

In addition, we assume the same set symbols for the compiled domain structure as in the proof of Theorem 20:
+  \# O  c :