Machines with Memory - Models of Computation: Exploring the Power of Computing - page 133

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 ∨