
| x      | SBIC    | SLIC     | SBC      | SBI     | S       | SLI   |
|------|---------|----------|----------|---------|---------|-------|
| 6p      | 6p         | 6c          | 6p          | 6p         |         |       |
| SBIC | Cor. 15 | Cor. 15  | Cor. 12  | Cor. 15 | Cor. 15 |       |
| 6c      | 6c         | 6c          |          |         |         |       |
| SLIC | v       | v        | Theo. 11 | Cor. 12 | Cor. 12 |       |
| 6c      | 6c         | 6c          | 6c          |         |         |       |
| SBC  | v       | Cor. 19  | Cor. 12  | Cor. 12 | Cor. 19 |       |
| 6p      | 6p         | 6p          | 6p          |         |         |       |
| SBI  | v       | Cor. 15  | Theo. 14 | Cor. 15 | Cor. 15 |       |
| 6c      | 6c         |          |          |         |         |       |
| S    | v       | Theo. 18 | v        | v       | Cor. 19 |       |
| SLI  | v       | v        | v        | v       | v       |       |

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

It is obviously possible to come up with a set of exponentially many operators that can do the same thing in one step. However, it is unclear how to do that with less than exponentially many operators.

In fact, we will show that this is impossible.

In order to illustrate this point, let us generalize the above example. We start with a set of n propositional atoms n p1; : : : ; pn and a disjoint copy of this set: \#
n p\#
i pi n .

Further, if S  cn, then S\#shall denote the corresponding set of literals over d\#

n , i.e.,

S# p# i pi S f:p# i pi S :

Consider now the following SLIC domain structure:

$${\mathcal{S}}$$

2n n # n ; O2n  h>; pi ) p# i ; pi ) p# i pi ngi; 2n h 2n; O2ni:

From the construction it follows that for all pairs I; G such that I is a consistent and complete set over cn and G  I\#, the instance h 2n; I; Gi has a one-step plan. Conversely, for all pairs I; G with G d\# 6 I\#, there does not exist a solution.

Trying to define a SBI domain structure polynomially sized in jj 2njj with the same property seems to be impossible, even if we allow for c-step plans. However, in trying to prove this, it turns out that an additional condition on the state-translation function is needed.

We say that the state-translation functions are **local** iff for all state specifications S and for 1 2 ; we have

$$t_{i}\quad_{1},S\quad_{1}^{--}\quad t_{g}\quad_{2},S\quad_{2}^{--}$$
2 ;: