Information Technology Reference
In-Depth Information
columns:
⎡
⎤
−
−
...
−
10
...
00
...
1
1
0
⎣
⎦
.
00 0
−
1
...
−
1
0
A
=
B
.
.
.
.
.
...
0
0
00
...
00
...
−
...
−
0
1
1
We show that the instance of 3-
SAT
is a “Yes” instance if and only if this instance of 0-1
INTEGER PROGRAMMING
is a “Yes” instance, that is, if and only if
A
x
=
d
.
We write the column
p
-vector
x
as the concatenation of the column
m
-vector
u
and
the column
mn
-vector
v
. It follows that
A
x
=
b
if and only if
A
u
b
.Nowconsider
the
i
th component of
A
u
.Let
u
select
k
i
uncomplemented and
l
i
complemented variables
of clause
c
i
.Then,
A
u
≥
≥
b
if and only if
k
i
−
l
i
≥
d
i
=
1
−
q
i
or
k
i
+(
q
i
−
l
i
)
≥
1
for all
i
.Nowlet
x
i
=
u
i
for 1
l
i
are the numbers of
uncomplemented and complemented variables in
c
i
that are set to 1 and 0, respectively.
Since
k
i
+(
q
i
−
≤
i
≤
n
.Then
k
i
and
q
i
−
l
i
)
≥
1,
c
i
is satisfied, as are all clauses, giving us the desired result.
8.11
The Boundary Between
P
and
NP
It is important to understand where the boundary lies between problems in
P
and the
NP
-
complete problems. While this topic is wide open, we shed a modest amount of light on it by
showing that 2-
SAT
,theversionof3-
SAT
in which each clause has at most two literals, lies on
the
P
-side of this boundary, as shown below. In fact, it is in
NL
, which is in
P
.
THEOREM
8.11.1
2-
SAT
is in
NL
.
Proof
Given an instance
I
of 2-
SAT
, we first insure that each clause has exactly two distinct
literals by adding to each one-literal clause a new literal
z
that is not used elsewhere. W
e
then construct a directed graph
G
=(
V
,
E
)
with vertices
V
labeled by the literals
x
and
x
for each variable
x
appearing
in
I
. This graph ha
s a
n edge
(
α
,
β
)
in
E
direct
ed
from vertex
α
to vertex
β
if the clause
(
α
∨
β
)
is in
I
.If
(
α
∨
β
)
is in
I
,sois
(
β
∨
α
)
because of
∨
.Thus,if
(
α
,
β
)
∈
E
,then
(
β
,
α
)
∈
E
also. (See Fig.
8.15
.) No
te
commutativity
of
that
(
α
,
β
)
=
γ
.
It follows that if there is a path from
α
to
γ
in
G
, there is a distinct path from
γ
to
α
obtained by reversing the directions of each edge on the path and replacing the literals by
their complements.
To understand why these edges are chosen, note that if all clauses of
I
are satisfied and
=(
β
,
α
)
because this requires that
β
=
α
, which is not allowed. Let
α
(
α
∨
β
)
is in
I
,then
α
=
1 implies that
β
=
1. This implication relation, denot
ed
α
⇒
β
,
i
s
transitive. If t
h
ere is a path
(
α
1
,
α
2
,
...
,
α
k
)
in
G
, then there are clauses
(
α
1
∨
α
2
)
,
(
α
2
∨
α
k
)
in
I
. If all clauses are satisfied and if the literal
α
1
=
1, then
each un-negated literal on this path must have value 1.
We now show that an instance
I
is
a
“No” instance
i
f and only if there is a variable
x
such that there is a path in
G
from
x
to
x
and one from
x
to
x
.
If there is a variable
x
such that such paths exists, this means that
x
α
3
)
,
...
,
(
α
k−
1
∨
⇒
x
and
x
⇒
x
which is a logical contradiction. This implies that the instance
I
is a “No” instance.
Conversely, suppose
I
isa“N
o
”instance.Toprovethereisavariable
x
such that there
are paths from vertex
x
to vertex
x
and from
x
to
x
, assume that for no variable
x
does this
Search WWH ::
Custom Search