the planning method. However, we also provide results that *separate* planning formalisms using results from computational complexity theory on circuit complexity and non-uniform complexity classes. Such separation results indicate that adding a particular language feature adds to the expressive power and to the difficulty of integrating the feature into an existing planning algorithm.

For example, we prove that conditional effects cannot be compiled away and that boolean formulae cannot be compiled into conditional effects—provided the plans in the target formalism are allowed to grow only linearly.

This answers the question posed in the beginning. The compilation approach proposed by Gazen and Knoblock (1997) cannot be more space efficient, even if we allow for linear growth of the plans in the target formalism.2Allowing for polynomial growth of the plans, however, the compilation scheme can be more space efficient. Interestingly, it seems to be the case that a compilation scheme that allows for polynomially larger plans is similar to the implementation of conditional effects in the IPP system (Koehler et al., 1997), Kambhampati and colleagues' (1997) planning system, and Anderson and colleagues' (1998) planning system.

The rest of the paper is structured as follows. In Section 2, we introduce the range of propositional planning formalisms analyzed in this paper together with general terminology and definitions.

Based on that, we introduce the notion of compilability between planning formalisms in Section 3.

In Section 4 we present polynomial-time compilation schemes between different formalisms that preserve the plan size exactly, demonstrating that these formalisms are of identical expressiveness.

For all of the remaining cases, we prove in Section 5 that there cannot be any compilation scheme preserving plan size linearly, even if there are no bounds on the computational resources of the compilation process. In Section 6 we reconsider the question of identical expressiveness by using compilation schemes that allow for polynomial growth of the plans. Finally, in Section 7 we summarize and discuss the results.

## 2. Propositional Planning Formalisms

First, we will define a very general propositional planning formalism, which appears almost as expressive as the propositional variant of ADL (Pednault, 1989). This formalism allows for arbitrary boolean formulae as preconditions, conditional effects and partial state specifications. Subsequently, we will specialize this formalism by imposing different syntactic restrictions.

## 2.1 A General Propositional Planning Formalism

Let  be the countably infinite set of propositional atoms or **propositional variables**. Finite subsets of  are denoted by . Further, is defined to be the set consisting of the constants (denoting truth) and (denoting falsity) as well as atoms and negated atoms, i.e., the **literals**, over . The **language of propositional logic** over the logical connectives ; , and and the propositional atoms is denoted by . A **clause** is a disjunction of literals. Further, we say that a formula '  is in **conjunctive normal form** (CNF) if it is a conjunction of clauses. It is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals.

Given a set of literals L, by pos L we refer to the **positive literals** in L, by neg L we refer to the **negative literals** in L, and by  L to the atoms used in L, i.e.,  L p p L or p