$$\begin{array}{r l}{{\dot{\imath}}}&{{}\leq}\end{array}$$
$\begin{array}{ccccc}\mbox{N}&\mbox{$\int$}&\mbox{$i$}&\leq\\ &\mbox{$i^{\prime}$}&\geq&i\end{array}$
4.2.2  DIFFICULTY  HEURISTIC

$$\mathbb{N}$$
$$\mathbb{N}$$
min {i | p o pE   (o)
$$i\}$$
$$\mathbb{N}$$

4.2.3  A CTION  S E T  L INE ARIZATION
N

$$\dot{i}$$
$$\dot{\vec{\mathrm{i}}}$$
$$\mathbf{\dot{i}}$$
o
$$\dot{i}$$

p

$$o^{\prime}\qquad\quad i$$
$$\,p$$

o ol NP
Definition 6  Let OPTIMAL ACTION LINEARIZATION denote the following problem.

0 K

$$f\quad{\mathcal{O}}\mapsto\{\ ,\quad\cdots,|{\mathcal{O}}|\}$$

K
Theorem 2  Deciding OPTIMAL ACTION LINEARIZATION is NP-complete.

Proof:
DIRE CT ED

  **Proof:**  OPTIMAL LINEAR ARRANGEMENT  $G$$V,A$$K$  $f$$V$$\mapsto$$\{\,\,,\,,\,,\,,\,,\,|V|\}$  $(u,v)$$\in$$A$$f$$v$$-$$f$$u$$\leq$$K$  $K$  $f$$u$$f$$v$$u,v$$A$
0 w

$$\begin{array}{r l}{w}&{{}\quad V}\\ {w}&{{}\quad V}\end{array}$$

$$u,v\qquad A$$
$$\begin{array}{c c c}{{w}}&{{}}&{{w}}&{{}}\\ {{}}&{{P_{w}^{(u\,,v)}}}&{{}}&{{R_{w}^{(u\,,v\,)}}}\end{array}$$
