+:> )(v + 2)

(y) (z)

Figure 10.7: Transforming a boolean expression into CNF

unnecessary, but we put them in CNF expressions to help remind you that we are talking about a product of clauses.

For an AND node, the construction of a CNF expression is simply to take the product (AND) of all the clauses for the two subexpressions. Thus, for instance, the node for the subexpression x{y + z) has an associated CNF expression that is the product of the one clause for x, namely (x), and the two clauses for у + z, namely {v + у)(г7 + z). *

For an OR node, we must introduce a new variable. We add it to all the clauses for the left operand, and we add its negation to the clauses for the right operand. For instance, consider the root node in Fig, 10.7. It is the OR of expressions xy and x{y + z), wliose CNF expressions have been determined to be (з:)(7) and (i)(v + y)(u + z), respectively. We introduce a new variable u, which is added without negation to the first group of clauses and negated in the second group. The result is

F = {xi + x){u + y){u + x){u + v+y){u + v + z)

Theorem 10.13 tells us that any truth assignment T that satisfies E can be extended to a truth assignment S that satisfies F. For instance, the assignment T{x) = 0, T{y) 1, and T{z) = 1 satisfies E. We can extend Г to 5 by adding S{u) = 1 and Siv) 0 to the requhed 3{х) 0, 5(y) - 1, and S{z) = I that we get from T. You may check that S satisfies F.

Notice that in choosing S, we were required to pick S(u) = 1, because T makes only the second part of E, that is x{y + z), true. Thus, we need S{u) = 1

in this special case, where the subexpression jf-Ь z is already a clause, we did not have to perform the general construction for the OR of expressions, and could have produced {ij 4- г) as the product of clauses equivalent toy + z. However, in this example, we stick to the general rules.

(u + X )(u + у ){u + X )(u + V + у ) (и + V + z )

(x ){y )

For convenience, we sliall talk of literals as if they were unnegated variables, like x. However, the constructions apply equally well if some or all of the literals are negated, like x.

to make true the clauses [u + x){u + y), which come from the first part of E. However, we could pick either value for v, because in the subexpression у + z, both sides of the OR are true according to T. □

10.3.4 NP-Completeness of 3SAT

Now, we show an even smaller class of boolean expressions with an NP-complete satisfiability problem. Recall the problem 3SAT is:

* Given a boolean expression E that is the product of clauses, each of which is the sum of three distinct literals, is E satisfiable?

Although the 3-CNF expressions are a small fraction of the CNF expressions, they are complex enough to make their satisfiability test NP-complete, as the next theorem shows.

Theorem 10.15: 3SAT is NP-complete.

PROOF: Evidently 3SAT is in AfV, since SAT is in AfV. To prove NP-completeness, we shall reduce CSAT to 3SAT. The reduction is as follows. Given a CNF expression £ = ei Л 2 Л Л e* we replace each clause as follows, to create a new expression F. The time taken to construct F is finear in the length of E, and we shall see that a truth assignment satisfies E if and only if it can be extended to a satisfying truth assignment for F.

1. If Ci is a single literal, say {x)° Introduce two new variables u and v. Replace (x) by the four clauses {x + u + v){x + u + v)ix + u+v)(x + u + v). Since и and v appear in all combinations, the only way to satisfy all four clauses is to make x true. Thus, all and only the satisfying assignments for E can be extended to a satisfying assignment for F.

2. Suppose €i is the sum of two literals, [x + y). Introduce a new variable z, and replace e; by the product of two clauses {x + y + z){x + y-\-z). As in case 1; the only way to satisfy both clauses is to satisfy {x + y).

3. If is the sum of three literals, it is already in the form required for 3-CNF, so we leave in the expression F being constructed.

4. Suppose fij = (xi +X2 H-----Vxm) for some m > 4. Introduce new variables

У11У2, , Ут-з and replace by the product of clauses

{xi + ХЧ + У\){х?. +ш+У2){х+У2 + Уг)--- /JQ2)

{Xm.-2 + j/rri + yjn-z){xm-\ + Хтп A Ут-з)

An assignment T that satisfies E must make at least one literal of true; say it makes Xj true (recall Xj could be a variable or a negated variable).

10.3.5 Exercises for Section 10.3

Exercise 10,3.1: Put the following boolean expressions into 3-CNF: * a) xy + xz.

b) wxyz + U + V.

c) wxy + xuv.

Exercise 10.3.2: The problem 4TA-SAT is defined as follows: Given a boolean expression E, does E have at least four satisfying truth assignments. Show that 4TA-SAT is NP-complete.

Exercise 10.3.3: In this exercise, we shall define a family of 3-CNF expressions. The expression has n variables, xi,X2, .. ,Xn- For each set of three distinct integers between 1 and n, £ has clauses {X1+X2+X3) and (хТ+х+Щ)-Is En satisfiable for:

*! a) n= 4?

!! b) n = 5?

! Exercise 10.3.4: Give a polynomial-time algorithm to solve the problem 2SAT, i.e., satisfiability for CNF boolean expressions with only two literals per clause. Hint: If one of two literals in a clause is false, the other is forced to be true. Start with an assumption about the truth of one variable, and chase down all the consequences for other variables.

Then, if we miake j/i, ,yj-2 true and make yj-i,yj,...,ут~з false, we satisfy all the clauses of (10.2). Thus, T may be extended to satisfy these clauses. Conversely, if T makes all the xs false, it is not possible to extend T to make (10.2) true. The reason is that there are m - 2 clauses, and each of the m - 3 ys can only make one clause true, regardless of whether it is true or false.

We have thus shown how to reduce each instance E of CSAT to an instance F of 3SAT, such that F is satisfiable if and only if E is satisfiable. The construction evidently requires time that is linear in the length of because none of the four cases above expand a clause by more than a factor 32/3 (that is the ratio of symbol counts in case 1), and it is easy to calculate the needed symbols of F in time proportional to the number of those symbols. Since CSAT is NP-complete, it follows that 3-SAT is likewise NP-complete. □