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

3.9.6 Reductions to NP -Complete Languages
Our first NP -complete language is CIRCUIT SAT , a language closely related to CIRCUIT
VALUE .

CIRCUIT SAT
Instance: A circuit description with n input variables

{ x 1 , x 2 , ... , x n }

for some integer n

and a designated output gate.
Answer: “Yes” if there is an assignment of values to the variables such that the output of the
circuit has value 1.

THEOREM 3.9.6 The language CIRCUIT SAT is NP -complete.
Proof To s h ow t h a t CIRCUIT SAT is NP -complete, we must show that it is in NP and that
every language in NP can be translated to it by a polynomial-time program. We have already
shown the second half of the proof in Theorem 3.9.1 . We need only show the first half. As
discussed in the proof of Theorem 3.9.5 , each circuit can be organized so that all steps on
which a given step depends precede it. We assume that a string in CIRCUIT SAT meets
this condition. Design an NTM which on such a string uses choice inputs to assign values
to each of the variables in the string. Then invoke the program described in the proof of
Theorem 3.9.5 to evaluate the circuit. For some assignment to the variables x 1 , x 2 , ... , x n ,
this nondeterministic program can accept each string in CIRCUIT SAT but no string not in
CIRCUIT SAT . It follows that CIRCUIT SAT is in NP .

The model used to show that a language is P -complete directly parallels the model used to
show that a language L 1 is NP -complete. We first show that L 1 is in NP and then show that
every language L NP can be translated to it in polynomial time. That is, we show that there

is a polynomial p and algorithm that on inputs of length n runs in time p ( n ) ,andthatfor
each string w the algorithm translates w into a string v such that w is in L if and only if v is
in L 1 . (This is called a polynomial-time reduction .) Since any algorithm that uses log-space
(as does the program in Fig. 3.27 ) runs in polynomial time (see Theorem 8.5.8 ), a log-space
reduction can be used in lieu of a polynomial-time reduction.
If we have already shown that a language L 0 is NP -complete, we can show that another
language, L 1 ,in NP is NP -complete by translating L 0 into L 1 with a polynomial-time algo-
rithm. Since the composition of two polynomial-time algorithms is another polynomial-time
algorithm (see Problem 3.2 ), every language in NP can be translated in polynomial time into
L 1 and L 1 is NP -complete. The diagram shown in Fig. 3.28 applies when the reductions
are polynomial-time and the languages are members of NP instead of P .Many NP -complete
languages are exhibited in Section 8.10 .
We apply this idea to show that SATISFIABILITY is NP -complete. Strings in this language
consist of strings representing the POSE (product-of-sums expansion) of a Boolean function.
Thus, they consist of clauses containing literals (a variable or its negation) with the property
that for some value of the variables at least one literal in each clause is satisfied.

∈

SATISFIABILITY
Instance: Asetof literals X = { x 1 , x 1 , x 2 , x 2 , ... , x n , x n } and a sequence of clauses

C =( c 1 , c 2 , ... , c m ) where each clause c i is a subset of X .
Answer: “Yes” if there is a (satisfying) assignment of values for the variables

{ x 1 , x 2 , ... ,

x n } over the set B such that each clause has at least one literal whose value is 1.