reducible to 3SAT.
We illustrate the reduction with the simple 4-literal expression
We introduce a new variable z and construct
If e 1 is true, one of the x 1 , x 2 , x 3 , x 4 must be true. If x 1 ∨ x 2 is true, we choose z =
0, and e 2 is true. If x 3 ∨ x 4 = 1, we can choose z = 1 to satisfy e2. Conversely, if
e 2 is true, e 1 must also be true, so for satisfiability, e 1 and e 2 are equivalent.
We claim that this pattern can be extended to clauses with more than four
literals, but we will leave the argument as an exercise. We include an exercise to
show that the conversion of a CNF expression from the SAT form to 3SAT form
can be done deterministically in polynomial time.
Example 14.10
The 3SAT problem is polynomial-time reducible to CLIQUE.
We can assume that in any 3SAT expression each clause has exactly three
literals. If in some expression this is not the case, we just add extra literals that
do not change the satisfiability. For example,(x 1 ∨ x 2 ) is equivalent to (x 1 ∨ x 1 ∨
x 2 ). Consider now the expression
Figure 14.3