Complexity Classes - Models of Computation: Exploring the Power of Computing - page 356

8.10.1 NP -Complete Satisfiability Problems
In Section 3.9.6 we showed that SATISFIABILITY defined below is NP -complete. In this sec-
tion we demonstrate that two variants of this language are NP -complete by simple extensions
of the basic proof that CIRCUIT SAT is NP -complete.

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 } B

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

The two variants of SATISFIABILITY are 3- SAT , which has at most three literals in each
clause, and NAESAT , in which not all literals in each clause have the same value.

3- SAT
Instance: A set of literals X =

, and a sequence of clauses
C =( c 1 , c 2 , ... , c m ) , where each clause c i is a subset of X containing at most three
literals.
Answer: “Yes” if there is an assignment of values for variables

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

{ x 1 , x 2 , ... , x n } over the set

B such that each clause has at least one literal whose value is 1.

THEOREM 8.10.1 3- SAT is NP -complete.
Proof The proof that SATISFIABILITY is NP -complete also applies to 3- SAT because each
of the clauses produced in the transformation of instances of CIRCUIT SAT hasatmostthree
literals per clause.

NAESAT
Instance: An instance of 3- SAT .
Answer: “Yes” if each clause is satisfiable when not all literals have the same value.

NAESAT contains as its “Yes” instances those instances of 3- SAT in which the literals in
each clause are not all equal.

THEOREM 8.10.2 NAESAT is NP -complete.

Proof We reduce CIRCUIT SAT to NAESAT using almost the same reduction as for 3- SAT .
Each gate is replaced by a set of clauses. (See Fig. 8.11 .) The only difference is that we
add the new literal y to each two-literal clause associated with AND and OR gates and to
the clause associated with the output gate. Clearly, this reduction can be performed in de-
terministic log-space. Since a “Yes” instance of NAESAT can be verified in nondeterministic
polynomial time, NAESAT is in NP . We now show that it is NP -hard.
Given a “Yes” instance of CIRCUIT SAT , we show that the instance of 3- SAT is a “Yes”
instance. Since every clause is satisfied in a “Yes” instance of CIRCUIT SAT ,everyclauseof
the corresponding instance of NAESAT has at least one literal with value 1. The clauses that
don't contain the literal y by their nature have not all literals equal. Those containing y can
be made to satisfy this condition by setting y to 0, thereby providing a “Yes” instance of
NAESAT .
Now consider a “Yes” instance of NAESAT produced by the mapping from CIRCUIT
SAT . Replacing every literal by its complement generates another “Yes” instance of NAESAT