Information Technology Reference
In-Depth Information
THEOREM
3.9.7
SATISFIABILITY
is
NP
-complete.
Proof
SATISFIABILITY
is in
NP
because for each string
w
in this language there is a sat-
isfying assignment for its variables that can be verified by a polynomial-time program. We
sketch a deterministic RAM program for this purpose. This program reads as many choice
variables as there are variables in
w
and stores them in memory locations. It then evalu-
ates each literal in each clause in
w
and declares this string satisfied if all clauses evaluate
to 1. This program, which runs in time linear in the length of
w
,canbeconvertedto
a Turing-machine program using the construction of Theorem
3.8.1
.Th sprogramex-
ecutes in a time cubic in the time of the original program on the RAM. We now show
that every language in
NP
can be reduced to
SATISFIABILITY
via a polynomial-time pro-
gram.
Given an instance of
CIRCUIT SAT
, as we now show, we can convert the circuit descrip-
tion, a straight-line program (see Section
2.2
), into an instance of
SATISFIABILITY
such that
the former is a “yes” instance of
CIRCUIT SAT
if and only if the latter is a “yes” instance
of
SATISFIABILITY
. Shown below are the different steps of a straight-line program and the
clauses used to replace them in constructing an instance of
SATISFIABILITY
. A determinis-
tic TM can be designed to make these translations in time proportional to the length of the
circuit description. Clearly the instance of
SATISFIABILITY
that it produces is a satisfiable
instance if and only if the instance of
CIRCUIT SAT
is satisfiable.
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
)
g
i
∨
g
k
)
g
i
∨
g
j
∨
g
k
)
(
i
AND
j
)
(
g
i
∨
g
j
)
g
i
∨
g
k
)
g
i
∨
g
j
∨
g
k
)
(
i
OUTPUT
j
)
(
g
j
)
For each gate type it is easy to see that each of the corresponding clauses is satisfiable
only for those gate and argument values that are consistent with the type of gate. For ex-
ample, a
NOT
gate with input
g
j
has value
g
i
=
1w
he
n
g
j
has value 0 and
g
i
=
0when
g
j
has value 1.
g
j
)
are satisfied.
However, if
g
i
is equal to
g
j
, at least one of the clauses is not satisfied. Similarly, if
g
i
is the
AND
of
g
j
and
g
k
, then examining all eight values for the triple
(
g
i
,
g
j
,
g
k
)
shows
that only when
g
i
is the
AND
of
g
j
and
g
k
are all three clauses satisfied. The verification
of the above statements is left as a problem for the reader. (See Problem
3.36
.) Since the
output clause
(
g
j
)
is true if and only if the circuit output has value 1, it follows that the
set of clauses are all satisfiable if and only if the circuit in question has value 1; that is, it is
satisfiable.
Givenaninstanceof
CIRCUIT SAT
, clearly a deterministic TM can produce the clauses
corresponding to each gate using a temporary storage space that is logarithmic in the length
of the circuit description because it need deal only with integers that are linear in the length
of the input. Thus, each instance of
CIRCUIT SAT
can be translated into an instance of
SATISFIABILITY
in a number of steps polynomial in the length of the instance of
CIRCUIT
SAT
. Since it is also in
NP
,itis
NP
-complete.
In both cases, both of the clauses
(
g
i
∨
g
j
)
and
(
g
i
∨
Search WWH ::
Custom Search