If we now have a closer look at what the power of c-step plan acceptance for families of SLC

domain structures is, it turns out that it is less powerful than NC1. In order to show that, we will first prove the following lemma that relates c-step SLC plans to circuits with gates of unbounded fan-in.

Lemma 17 Let h ; Oi *be a* SLC domain structure, let G  , and let be a c-step plan over
. Then there exists a polynomially sized boolean circuit C *with unbounded fan-in and depth* 7c+ 2 such that is a plan for h ; I; Gi iff the circuit C *has value 1 for the input* wI .

Proof. The general structure of a circuit for a c-step SLC plan is displayed in Figure 5. For each

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

```
plan step (or level) j and each atom pi, there is a connection p
                                                                   j
                                                                   
                                                                   i
                                                                   
                                                                    . The connections on level are

```

the input gates, i.e., p0 i xi. The goal test is performed by an -gate that checks that all the goals are true on level c, in our case G p1; p2; pn . Further, using the -gate, it is checked that no inconsistency was generated when executing the plan.

For each plan step j, it must be computed whether the precondition is satisfied and what the result of the conditional effects are. Figure 6 (a) displays the precondition test for the precondition p1; p2; p3 . If the conjunction of the precondition literals is not true, k becomes true, which is connected to the -gate in Figure 5.

Without loss of generality (using a polynomial transformation), we assume that all conditional effects have the form L ) l. Whether the effect l is activated on level j is computed by a circuit as displayed in Figure 6 (b), which shows the circuit for p1; p3 ) pi .

Finally, all activated effects are combined by the circuit shown in Figure 6 (c). For all atoms pi ,
we check whether both pi and pi have been activated, which would set r true. This is again one of the inputs of the -gate in Figure 5. If neither pi nor pi have been activated, the value of pi on level j is determined by the value of pi on level j. Otherwise the value of pi on level j is determined by the value of p e;j i
, i.e., the activation value of the positive effect pi on level j.

The depths of the circuits in Figure 6 (b) and (c) dominate the depth of the circuit necessary to represent one plan step leading to the conclusion that a plan step can be represented using a circuit of depth 7. Adding the depth of the goal testing circuit, the claim follows.

The lemma implies that SLC c-step plan acceptance is indeed less powerful than S 1-step plan acceptance, which means that a compilation scheme from S to SLC preserving plan size linearly is impossible.