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

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

∨