
| operator   | precond   | postcond.   |
|------------|-----------|-------------|
| i, 1       |           |             |
| i, 2       |           |             |
| 1, 3       | 7         | 1, 3        |
| i, 1       | i, 1      |             |
| i, 1       | i, 1      | -           |
| i 2        | 1 1 2     | i 2         |
| i 2        | i 2       | 1 1 2       |
| 1, 3       | 1 1 3     | i 3         |
| -          |           |             |

only if: Suppose    is not satisfiable. Further suppose that    is a minimum reordering of and that as a parallel execution of length 8 or shorter for . Wlg. assume that every action is released as early as possible by . Then, according to the observation above it must hold for each , 1
, that either f ) = 0    (
( = 3 or
( ) = 0    ( ) = 1   ( ) = 2    ( ) = 3 Hence, exactly one of the atoms is of length 8, it follows from the earlier observation that for all   , 1 2 for some 1 3. Hence, j,k = j for some j since j is n-valid and j is a parallel execution for Define an interpretation s.t. for all , 1

$$\left(\begin{array}{c}{{\textrm{i}}}\end{array}\right)=$$
 $\large\text{if}\quad\overset{*}{i}=$  •th exercise. 

otherwise However, this interpretation is obviously a model for , which contradicts the assumption.

It follows that must be of length 9 or longer.

This concludes the proof and shows that    is satisfiable iff    has a reordering with a parallel execution of length 8 or not.

□
Theorem  7.11  MINIMUM PARALLEL DEORDERING cannot approximate MINIMUM
PARALLEL REORDERING within |  | k  for any constant   ≥ 0.

Proof:   The proof assumes GT plans and simple concurrency.  First, define the generic actions 

$$\mathbf{\Phi}_{i}^{k}\left(\mathbf{\Phi}\mathbf{\Phi}\right)=$$
$$\begin{array}{l l}{{\hat{k}}}&{{\cdot}}\\ {{(i-1\,)m+1}}\end{array}\left(\begin{array}{l l}{{}}&{{}}\\ {{}}&{{}}\end{array}\right)$$

plans

( i − 1 ) m + 1 ( 1 )
for
= 1