
## 5.3 On The Expressive Power Of Partial State Specifications And Boolean Formulae

In all the cases considered so far, operators over partial state specifications could be compiled to operators over complete state specifications, i.e., partial state specifications did not add any expressiveness. This is no longer true, however, if we also allow for arbitrary boolean formulae in preconditions and effect conditions. In this case, we can decide the coNP-complete problem of whether a formula is a tautology by deciding whether a one-step plan exists. Asking, for example, if the SBI -instance h ; fh'; gig; ;; ggi has a plan is equivalent to asking whether ' is a tautology.

Let the **one-step plan existence problem** (1-PLANEX) be the PLANEX problem restricted to plans of size one. From the above it is evident that SBIC -1-PLANEX and SBI -1-PLANEX are coNP-hard. Let p be some fixed polynomial, then the **polynomial step plan-existence problem**
(p-PLANEX) is the PLANEX problem restricted to plans that have length bounded by p n , if n is the size of the planning instance. As is easy to see, this problem is in NP for all formalisms except SBIC and SBI . The reason is that after guessing a sequence of operators and state specifications of polynomial size, one can verify for each step in polynomial time that the precondition is satisfied by the current state specification and produces the next state specification. Since there are only polynomially many steps, the overall verification takes only polynomial time.

Proposition 13 X -p-PLANEX *can be solved in polynomial time on a nondeterministic Turing machine for all formalisms different from* SBIC and SBI .

From the fact that SBI -1-PLANEX is coNP-hard and, e.g., SBC -p-PLANEX is in NP, it follows almost immediately that there is no *polynomial-time* compilation scheme from SBI to SBC that preserves plan length polynomially (if NP 6 coNP). However, even if we allow for unbounded computational resources of the compilation process, a proof technique first used by Kautz and Selman (1992) can be used to show that such a compilation scheme cannot exist (provided p 3 6p 3).

```
Theorem 14 SBI cannot be compiled to SBC preserving plan size polynomially, unless p
                                                                      3
                                                                      
                                                                           p
                                                                           
                                                                           3.

```

Proof. Let ' be a propositional formula of size n in conjunctive normal form with three literals per clause. As a first step, we construct for each n a SBI domain structure n with size polynomial in n and the following properties. Unsatisfiability of an arbitrary 3CNF formula ' of size n is equivalent to -step plan existence for the SBI - -PLANEX instance h n; I'; ggi, where I' can be computed in polynomial time from '.

Given a set of n atoms, denoted by Pn, we define the set of clauses An to be the set containing all clauses with three literals that can be built using these atoms. The size of An is O n3, i.e.,
polynomial in n. Let Dn be a set of new atoms pfl1 ;l2;l3g corresponding one-to-one to the clauses in An. Further, let

 l1 l2 l3 pfl1;l2;l3g l1; l2; l3 An  :
$$\Phi_{n}$$
We now construct a SBI domain structure n h n; Oni for all formulae of size n as follows:

$$\begin{array}{c c c c}{{}}&{{}}&{{}}&{{P_{n}}}&{{\mathbf{D}_{n}}}&{{}}&{{g}}\\ {{}}&{{}}&{{}}&{{}}&{{}}\\ {{\mathbf{O}_{n}}}&{{}}&{{}}&{{\left\langle\begin{array}{c c c}{{}}&{{\Phi_{n}}}&{{,}}&{{g}}\end{array}\right\rangle}}\end{array}.$$
