as determined by . Let 1 . . . . . be a se uence consisting of e actly those operators such that     = true, followed by those operators such that = ; and
.

i = true or =     i and     = false, and finally s takes the initial state to a state t such that t = sat. Therefore has a solution.

sume has a solution. Take any assignment 1 not truth values to 1 be a propositional model such that a
= and for all Let
= ; i  ; =
true. Now there is a set uence 1 of operators taking to to t such that t = sat.

or all assign true to  ; if
; occurs in 
, and false otherwise.  t is easy to show that the assignment to   1 n l satisfies Q. Therefore is satisfiable.

□
onditional planning is also no harder than problems on the second level of the poly nomial hierarchy.   or conditional plans of polynomial si e it is easy to show that finding a plan is in the comple ity class machine that runs in polynomial time and uses an oracle for a problem in NP. The Turing machine first guesses a polynomial length string that represents a candidate plan. The oracle then checks whether it is the case that under some circumstances the goals cannot be reached. The oracle is represented by a nondeterministic Turing machine that guesses truth values for all contingent facts in nondeterministic polynomial time , and then e  ecutes the plan  in deterministic polynomial time  and accepts if a goal state was not reached.  The computation of the oracle is clearly in NP.   s our Turing machine runs in nondeterministic polynomial time with an NP oracle, the problem it solves is in The comple ity of classical planning is known in detail.   ylander shows that tion classical planning in finite domains is P  P
complete. Possibility of tractable planning under syntactic restrictions on the plan operators has been investigated by    ylander and by ackstrom and Nebel
. Tractability can be achieved only with very severe syntactic restrictions.

## 4. Encodings Of Conditional Planning As Quantified Boolean Formulae

e have devised several translations of conditional planning to   uantified    oolean formulae.

There are three separate issues in the translation of conditional planning to  uantified olean formulae.  The first, that is no di erent from translating classical planning to propositional logic, is the encoding of e ecutions of plans. The correspondence between plan e ecutions and plans is not as close as in classical planning, as one plan may have several di erent e ecutions. The second issue is the representation of plans.  Plans are ob ects that map a state to the operators to be e ecuted for producing a successor state.

The third issue, specific to , is the representation of uantification over all initial states and other uncertainties. n  ections . .  and . .  we propose two ways of doing this.

Unlike in classical planning where plans simply specify a se uence of operators that are e ecuted consecutively and the state of the environment after each operation is unam biguously known already at the planning time, conditional plans have to be able to behave di erently under di erent circumstances.  or e ample, the environment may be di erent on di  erent e  ecutions of the plan and there may be nondeterministic events a  ecting plan e ecution. The di  erent responses re  uired from conditional plans can be handled by defin ing conditional plans as ob ects with an internal state that re ects the current and earlier