Thus, the complement of PLANSAT can be polynomially reduced to FLORDER. As PSPACE = co-PSPACE, we are done. Theorem 2 Let R_ORDER denote the following problem:
Given two atomic facts A and B i as well as an action set O and an initial state Z i does B ≤ r A hold ?

Deciding RORDER is PSPACE-hard.

Proof: The proof proceeds by polynomially reducing PLANSAT to R_ORDER.

Let I, G, and O be the initial state, the goal state, and the action set in an arbitrary STRIPS planning instance. Let A, B, C, and D be new atomic facts not contained in the instance so far. We define the new action set O ′ by setting

$$\mathcal{O}^{\prime}:=\mathcal{O}\cup\left\{\begin{array}{l l l l}{{o_{I_{1}}}}&{{=\{C\}}}&{{\quad\to\mathrm{\ADD\}\{A,D\}\mathrm{\DEL\}\{C\},}}\\ {{o_{I_{2}}}}&{{=\{A,D\}}}&{{\quad\to\mathrm{\ADD\}\mathcal{I}\mathrm{\ DEL\}\{D\},}}\\ {{o_{G}}}&{{=\mathcal{G}}}&{{\quad\to\mathrm{\ADD\}\{B\}\mathrm{\ DEL\}\emptyset}}\end{array}\right\},$$
 -  $\mathrm{\underline{\text{ital state}}}$ by . 
and the new initial state by

$$T^{t}:=\{C\}$$

As in the proof of Theorem 1, the intention behind these definitions is to make solvability of the original problem equivalent to reachability of B from A . For reasonable orderings, reachability is concerned with actions that do not delete A, which is why we need the safety condition D .

Precisely, the only way to achieve A is by applying o I , to I ′ , i.e., per Definition 5 the only state s(A,-B) is {A, D}. As no action in the new operator set O' deletes A, we have the following sequence of equivalences.

B <, A &  V s(A,-B) -3 POA : B E Result(s(A,-B); POA) cf. Definition 8 ¬¬°² :  B E Result({A,D},P°'a) {A, D} is the only reachable state S{A,¬B} f ¬¬°° :  B E Result({A, D}, P°') no action in O'deletes A f
f
¬¬ P° such that  G ⊆ Result(I, P°)
with the definition of Of

f no solution plan exists for I, G, O
Thus, the complement of PLANSAT can be polynomially reduced to R_ORDER. With PSPACE = co-PSPACE, we are done.

Consequently, finding reasonable and forced ordering relations between atomic goals is already as hard as the original planning problem and it appears unlikely that a planner will gain any advantage from doing that. A possible way out of the dilemma is to define new ordering relations, which can be decided in polynomial time and which are, ideally, sufficient for the existence of reasonable or forced goal orderings. In the following, we introduce two such orderings.