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

CIRCUIT SAT

3- SAT SATISFIABILITY NAESAT

0-1 INT . PROGR . 3- COLORING

INDEPENDENT SET

TASK SEQUENCING

SUBSET SUM EXACT COVER

Figure 8.12 The succession of reductions used in this chapter.

distinct new variables to each clause that contains fewer than three literals can be done in
log-space, this new problem, which we also call 3- SAT ,isalso NP -complete.
We now construct an instance of INDEPENDENT SET from this new version of 3- SAT
in which k is equal to the number of clauses. (See Fig. 8.13 .) Its graph G has one triangle
for each clause and vertices carry the names of the three literals in a clause. G also has an
edge between vertices carrying the labels of complementary literals.
Consider a “Yes” instance of 3- SAT . Pick one literal with value 1 from each clause.
This identifies k vertices, one per triangle, and no edge exists between these vertices. Thus,
the instance of INDEPENDENT SET is a “Yes” instance. Conversely, a “Yes” instance of
INDEPENDENT SET on G has k vertices, one per triangle, and no two vertices carry the
label of a variable and its complement because all such vertices have an edge between them.
The literals associated with these independent vertices are assigned value 1, causing each
clause to be satisfied. Variables not so identified are assigned arbitrary values.

x 1 x 1 x 1

x 2 x 3 x 2 x 3 x 2 x 3

Figure 8.13 A graph f or an instanc e of INDEPENDENT SET constructed from the following
instance of 3- SAT : ( x 1 ∨ x 2 ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 3 ) .