Information Technology Reference
In-Depth Information
jm
k
+1. In the lower half of the base grid we translate and mirror the resulting
E-shape as follows. We let
B
i
occupy the cells between rows 2
m
+2
−
−
l
+
i
−
1 and
2
m
+2
l
+
i
and the three columns are shifted to the left by the number of occurrences
of the respective variable in negative clauses (Fig. 4(b)). Since each variable cell is
m
columns wide, we can always assign each clause to a uniquecolumn of
x
j
in the top
and bottom half of the grid in this way.
We actually fix
B
i
to the base grid by adding one shared element for each crossed
edgeofagrid cell to both
B
i
and the respective edgeblockof
−
Q
1
that does not share
an element with a vertex block in
contains such a block in
each partition and for each grid edge). No two blocks of the same clause type (positive
or negative) intersect, but blocks of different type do intersect in certain grid cells. For
each grid cell shared between a positive and negative block (except for the
n
variable
cells) we add one shared element (black dots in Fig. 4(b)) and call the respective grid
cell the
home cell
for this element. Recall that the orders of the incoming blocks from
the top and the bottom of each variable cell are inverted. Thus, within each variable
cell the blocks of each pair of a positive and negative clause using the corresponding
variable intersect, but no shared element is added. We denote the resulting new pair of
partitions as
Q
0
(recall that
{Q
0
,
Q
1
}
P
1
}
˕
and observe that its size is polynomial in the size of
˕
.
Next we argueaboutthestrong embedding options in contrast to the immediate em-
bedding for a clause block
B
i
in
{P
0
,
P
1
}
˕
. In the intermediate embedding each block
has three connections through variable cells linking the upper E-shape with the lower
E-shape. Any element shared with an edge block of the uniquely embedded base grid
must obviously be reached by the block region of
B
i
. Since the block region must be
simple, any strong embedding of
B
i
results from opening the intermediate embedding
of
B
i
in exactly two grid cells so that the resulting block region of
B
i
is connected and
has no holes. Additionally, a shared element must be placed in any intersection of the
block region of
B
i
with block regions of other clause blocks.
First we assume that
˕
is a satisfiable formula and a satisfying variable assignment
is given. We need to show that
{P
0
,
{P
0
,P
1
}
˕
has a strong embedding.Ifavariable
x
j
has
the value
true
in the given assignment we open all blocks of negative clauses using
x
j
in the corresponding variable cell; if
x
j
is
false
we open all blocks of positive clauses
using
x
j
.Thus no blocks intersect in variable cells any more. If a clause contains more
than one
true
literal, we open all but one connection in its variable cells of
true
literals.
Since the assignment satisfies
˕
, we know that each clause block is opened exactly
twice in its variable cells and thus forms a valid simple block region. Moreover, we
place all shared elements in their home cells so that every block intersection contains
an element and the embedding is strong. We call a strong embedding of
{P
0
,
P
1
}
˕
with
the above properties a
canonicalembedding
.
Now assume that
P
1
}
˕
has a strong embedding. We know that the base grid
has its unique embedding and that each block is embedded as a simple region that
results from opening the intermediate embedding (with its two E-shapes linked through
three variable cells) in exactly two cells. If the embedding is already canonical, we
can immediately construct a satisfying variable assignment for
˕
: if a variable cell is
crossed by clause blocks in
{P
0
,
Q
0
we set the variable to
true
, otherwise we set it to
false
.
Since every clause block is connected we know that this assignment satisfies all clauses.
