DEFINITION 4.3 The search problem MINIMAL-CONSTRAINED DEORDERING (MLCD) is defined as follows:
Given:  A PPI Π and a Π-valid plan Output: A minimal-constrained deordering of wrt. II
Theorem 4.4 MLCD can be solved in polynomial time if validity for p.o. plans can be tested in polynomial time.

' be the plan output by Proof:
Consider algorithm MLD in Figure 7 and let 
=
. The plan - is obviously a valid deordering of the algorithm on input l ww I. It is further obvious from the termination condition in the while loop that there is no
" is n-valid. It follows that   is a minimal-constrained other ordering
" 
deordering. Since the algorithm obviously runs in polynomial time, the theorem follows.

□
Furthermore, if validity testing is expensive, this will be the dominating cost in the MLD algorithm.

Corollary 4.5 If validity testing for p.o. plans can be solved in time  ( ( )) for some function  ( ), then MLCD can be solved in   (max   7/2   2  ( ) ) time.

procedure MLD
1 Input: A valid p.o. plan    = ( 
2 Output:  A minimal deordering of 3 while there is some   ∈ × s.t. (    ( × − {  } ) † ) is Π-valid  do 4 5 remove  from &
return (
6 Figure 7: The minimal-deordering algorithm MLD
In particular, note that plan validation is polynomial for the usual variant of propositional STRIPS without conditional actions (Nebel & Backstrom, 1994, Theorem 5.9).

More precisely, this proof pertains to the Common Propositional STRIPS formalism (CPS)
and, thus, holds also for the other common variants of propositional STRIPS, like Ground TWEAK (Backstrom, 1995). Furthermore, note that in practice it may not be necessary to compute the transitive closure either for the output plan or for validating a plan in the algorithm.

While minimum de-/reordering are stronger criteria than minimal deordering, they are also more costly to achieve. DEFINITION 4.6 The decision problem MINIMUM-CONSTRAINED DEORDERING (MMCD)
is defined as follows:
Given:  A PPI Π, a Π-valid plan and an integer   ≥ 0.

Question: Is there a deordering
..

o f s. t.

-