LEMMA 1 FAP N SA = 0 holds for all states SA satisfying A E SA that are reachable from I using actions from O.

The proof follows immediately from the definitions of "level-off" and "two propositions being mutual exclusive" given in (Blum & Furst, 1997).

We now provide a simple test which is sufficient for the existence of a reasonable ordering B <, A between two atomic goals A and B. Definition 10 (Efficient Ordering ≤ e ) Let ( O, I, G ≥ { A, B} ) be a planning problem.

Let FAp  be the False set for A. The ordering B ≤ e A holds if and only if
∀ o ∈ O A  : B  ∈ add(o) ⇒ pre(o) ∩ F G P  ≠ ∅
This means, B is ordered before A if the reduced action set only contains actions, which either do not have B in their add lists or if they do, then they require a precondition which is contained in the False set. Such preconditions can never hold in a state satisfying A and thus, these actions will never be applicable.

## Theorem 3 B ≤ E A ⇒ B ≤ R A

Proof: Assume that B &, A, i.e., B E Result(s(A,-B), POA) for a reachable state s(A,-B)
with A E s(A,-B); B & s(A,-B); and a Plan POA = (01, . . . , on) where oi E OA for 1 < i < n.

As A & del(o,) for all i (Definition 6), we have A E Result(s(A,¬B); (01,..., 0;)) for 0 ≤ i ≤ n and, with Lemma 1, FAP ∩ Result (s ( A ,¬ B ) ; ( 01 , . . , o i ) =  ∅  for  0 ≤ i ≤ n
(2)
Furthermore, as B & s(A,-B), but B E Result(s(A,-B),(O1,...,on)), there must be a step which makes B true, i.e.,
31 ≤ k ≤ n : B & Result( s(A,¬B); (o1,···,ok-1)) ∧ B ∈ Result( s(A,¬B); (o1,···,ok))
For this step, we obviously have B E add( ok ) and consequently, with the definition ooo B ≤ e A pre(o k ) N F A p ̸ = ∅ . Now, as o k must be applicable in the state where it is executed (otherwise it would not add anything to this state), the preconditions of ok must hold, i.e., pre(ok) ⊆ Result(s(A,-B); (01; . . ,ok –1)). This immediately leads to F AP ∩
Result(s(A,-B); (01, . . . , ok-1)) f 0, which is a contradiction to Equation (2). Quite obviously, the ordering ≤ e can be decided in polynomial time.

Theorem 4 Let E_ORDER denote the following problem:
Given two atomic facts A and B t as well as an initial state I and an action set O t does B ≤ e A hold ?

Then, E_ORDER can be decided in polynomial time: E_ORDER E P.