Information Technology Reference
In-Depth Information
Step Type
Corresponding Clauses
(
i
READ
x
)
(
g
i
∨
x
)
(
g
i
∨
x
)
(
i
NOT
j
)
(
g
i
∨
g
j
)
(
g
i
∨
g
j
)
(
i
OR
j
)
(
g
i
∨
g
j
∨
y
)
g
i
∨
g
k
∨
y
)
g
i
∨
g
j
∨
g
k
)
(
i
AND
j
)
(
g
i
∨
g
j
∨
y
)
g
i
∨
g
k
∨
y
)
g
i
∨
g
j
∨
g
k
)
(
i
OUTPUT
j
)
(
g
j
∨
y
)
Figure 8.11
A reduction from
CIRCUIT SAT
to
NAESAT
is obtained by replacing each gate
in a “Yes” instance of
CIRCUIT SAT
by a set of clauses. The clauses used in the reduction from
CIRCUIT SAT
to 3-
SAT
(see Section
3.9.6
) are those shown above with the literal
y
removed. In
the reduction to
NAESAT
the literal
y
is added to the 2-literal clauses used for
AND
and
OR
gates
and to the output clause.
since the literals in each clause are not all equal, a property that applies before and after
complementation. In one of these “Yes” instances
y
is assigned the value 0. Because this is a
“Yes” instance of
NAESAT
, at least one literal in each clause has value 1; that is, each clause
is satisfiable. This implies that the original
CIRCUIT SAT
problem is satisfiable. It follows
that an instance of
CIRCUIT SAT
has been translated into an instance of
NAESAT
so that the
former is a “Yes” instance if and only if the latter is a “Yes” instance.
8.10.2 Other
NP
-Complete Problems
This section gives a sampling of additional
NP
-complete problems. Following the format of
the previous section, we present each problem and then give a proof that it is
NP
-complete.
Each proof includes a reduction of a problem previously shown
NP
-complete to the current
problem. The succession of reductions developed in this topic is shown in Fig.
8.12
.
INDEPENDENT SET
Instance:
Agraph
G
=(
V
,
E
)
and an integer
k
.
Answer:
“Yes”ifthereisasetof
k
vertices of
G
such that there is no edge in
E
between
them.
THEOREM
8.10.3
INDEPENDENT SET
is
NP
-complete.
Proof
INDEPENDENT SET
is in
NP
because an NDTM can propose and then verify in
polynomial time a set of
k
independent vertices. We show that
INDEPENDENT SET
is
NP
-
hard by reducing 3-
SAT
to it. We begin by showing that a restricted version of 3-
SAT
,one
in which each c
la
use contains exactly three literals, is also
NP
-complete. If for some variable
x
,both
x
and
x
are in the same clause, we eliminate the clause since it is always satisfied.
Second,
w
e replace each 2-literal clause
(
a
∨
b
)
with the two 3-literal clauses
(
a
∨
b
∨
z
)
and
(
a
∨
b
∨
z
)
,where
z
is a new variable. Since
z
is either 0 or 1, if all clauses are satisfied then
(
a
b
)
has value 1 in both causes. Similarly, a clause with a single literal can be transformed
to one containing three literals by introducing two new variables and replacing the clause
containing the single literal with four clauses each containing three literals. Since adding
∨
Search WWH ::
Custom Search