su  ciently e  pressive notions of conditional plans.   or more restricted kinds of conditional plans the e istence of separate classical plans for every initial state does not guarantee the e istence of a conditional plan covering all initial states.  n these cases proofs of hardness of plan e istence have to be di erent, of course provided that the problems are indeed       hard and not easier. 

necessarily imply the e istence of conditional plans for e ample when it is not possible to combine any two plans that work under di erent circumstances to a conditional plan that works correctly whenever one of the constituent plans does. 1. Definition 1 A problem instance in conditional planning is a triple where is a set of literals (characterizing the initial states), members of    are pairs
(the operators) where and are sets of literals, and is a literal (the goal).

A problem instance has a solution if for every initial state (a propositional model)
such that
=  there is a sequence  1       n of operator applications that transform the initial state    to a state   ' such that   ' =     The application of in that      =    and for the following state that do not occur in ,   i =   if and only if   i+1 =  . Theorem 2 The problem of existence of solutions for problem instances in conditional planning is Proof:   e show that for any  uantified   oolean formula with prefi   V3 there is a problem instance in conditional planning such that the formula is true if and only if the problem instance has a solution. or the uantified formula to be true, for all truth values for the universal variables it has to be possible to assign truth values to the e istential variables sset that the un uantified formula evaluates to true.  n the planning setting this can be simulated as follows. The universal variables correspond to facts in the initial state that can be both true or false. or each initial state there has to be a se uence of operations that assigns the e  istential variables truth values that make the un  uantified formula true.

be any  uantified  oolean formula ∀ 1 ··· n 3 1 ··· m Φ where Φ consists of Let e construct a problem instance and show that a is true if and only if clauses.

has a solution.   onstructing   takes polynomial time on the length of   .  This shows that testing the e  istence of solutions in conditional planning is       hard.

efine
= sat, where

sa t and m l t sa t l m l t 1  V ..
n the initial states the variables   i may have any value and variables   i are all false. The can be e  ecuted to make variables   i true. The truth of clauses    in Φ can operators be verified by e ecuting operators inally, the operator    1 sat can be t applied to produce the goal if all clauses are true. The variable is needed to prevent false formulae appear true, like ∃
by the plan l ssssss 2 sume that for all assignments of truth values to true. Take any initial state     that satisfies     Now     determines an assignment of truth n. Let l m be the respective truth values for   1 values nt to to t