Information Technology Reference
In-Depth Information
C
1
=(
x
1
∨ x
1
∨ x
2
)
C
2
=(
x
2
∨ x
3
∨ x
5
)
C
3
=(
x
3
∨ x
4
∨ x
5
)
C
4
=(
x
2
∨ x
5
∨ x
6
)
C
5
=(
x
2
∨ x
3
∨ x
4
)
C
6
=(
x
2
∨ x
4
∨ x
6
)
C
7
=(
x
1
∨ x
2
∨ x
6
)
(a) Monotone rectilinear representation of a formula
˕
C
4
C
3
C
1
C
2
x
1
x
2
x
3
x
4
x
5
x
6
C
5
C
6
C
7
C
4
C
3
C
2
C
1
x
1
x
2
x
3
x
4
x
5
x
6
C
5
C
6
C
7
(b) Sketch of the clause blocks laid on top of the grid
{Q
0
, Q
1
}
(empty columns omitted)
Fig. 4.
Illustration of the
NP
-hardness reduction
proper grid-like embedding. We call
the
base grid
and the
n
special cells
between rows
m
and
m
+1the
variable cells
of the base grid.
Next we augment the pair of partitions
{Q
0
,
Q
1
}
{Q
0
,
Q
1
}
by additional blocks, one for each
clause, where positive clauses are added to
Q
1
. The defini-
tion of these
clause blocks
closely follows the layoutofthegiven MRR, see Fig.4(a).
Let
C
1
,C
2
,...,C
l
be the positive clauses of
˕
ordered so that if
C
i
is nested inside
the E-shape of
C
j
in the given MRR then
i<j
.Analogously let
C
l
+1
,...,C
m
be
the ordered negative clauses. We describe the definition of the block
B
i
for a positive
clause
C
i
(1
≤ i ≤ l
); blocks for negative clauses are defined symmetrically. We create
an
intermediate embedding
of
B
i
(which is not yet strong but serves as a template for
a later strong embedding)byputting
B
i
on top of the base grid
2
Q
0
and negative clauses to
and adding new ele-
ments to
B
i
and to certain edgeblocksin
Q
1
.Thisfixes
B
i
to runthrough two mirrored
E-shaped sets of grid cells of our choice (Fig.4(b)).Intheupper half of the base grid,
B
i
is assigned to run between rows
m
i
+1.Furthermore,
B
i
is assigned
to three columns leading towards the variable cells from the top. Let
x
j
beavariable
contained in
C
i
and assume that
C
i
is the
k
-th positive clause from the right connecting
to
x
j
in the embedding of the given MRR. Then
B
i
runs between columns
jm
−
i
and
m
−
−
k
and
2
Theideaoffixing paths to an underlyinggrid is inspired by Chaplick et al. [7].