* f) Complementation.

Exercise 10.1.7: jVP is also closed under each of the operations hsted for V in Exercise 10.1.6, with the (presumed) exception of (f) complementation. It is not known whether or not MV is closed under complementation, an issue we discuss further in Section 11.1. Prove that each of Exercise 10.1.6(a) through (e) hold for Jr.

10.2 An NP-Complete Problem

We now introduce you to the first NP-complete problem. This problem - whether a boolean expression is satisfiable - is proved NP-complete by explicitly reducing the language of any nondeterministic, polynomial-time TM to the satisfiability problem.

10.2.1 The Satisfiability Problem

The boolean expressions are built from:

1. Variables whose values are boolean; i.e., they either have the value 1 (true) or 0 (false).

2. Binary operators Л and V, standing for the logical AND and OR of two expressions.

3. Unary operator standing for logical negation.

4. Parentheses to group operators and operands, if necessary to alter the default precedence of operators: highest, then Л, and finally V.

Example 10.6; An example of a boolean expression is a; л -i(y V z). The subexpression у V 2 is true whenever either variable у or variable z has the value true, but the subexpression is false whenever both у and z are false. The larger subexpression ->(y V z) is true exactly when у W z is false, that is, when both у and z are false. If either у or z or both are true, then -i(y V .г) is false.

Finally, consider the entire expression. Since it is the logical AND of two subexpressions, it is true exactly when both subexpressions are true. That is, X л -(у V z) is true exactly when x is true, у is false, and z is false, □

A truth assignment for a given boolean expression E assigns either true or false to each of the variables mentioned in E. The value of expression E given a truth assignment Г, denoted E{T), is the result of evaluating E with each variable x replaced by the value T{x) (true or false) that T assigns to x.

A truth assignment T satisfies boolean expression E if E{T) = 1; i.e., the truth assignment T makes expression E true. A boolean expression E is said to be satisfiable if there exists at least one truth assignment T that satisfies E.

Example 10.7: The expression x A {y V z) of Example 10.6 is satisfiable. We saw that the truth assignment T defined by T{x) - 1, T{y) = 0, and T{z) = 0 satisfies this expression, because it makes the value of the expression true (1). We also observed that T is the only satisfying assignment for this expression, since the other seven combinations of values for the three variables give the expression the value false (0).

For another example, consider the expression E = x A {-x V y) A y. We claim that E is not satisfiable. Since there are only two variables, the number of truth assignments is 2 = 4, so it is easy for you to try all four assignments and verify that E has value 0 for all of them. However, we can also argue as follows. E is true only if all three terms connected by Л are true. That means x must be true (because of the first term) and у must be false (because of the last term). But under that truth assignment, the middle term ->x V у is false. Thus, E cannot be made true and is in fact unsatisfiable.

We have seen an example where an expression has exactly one satisfying assignment and an example where it has none. There are also many examples where an expression has more than one satisfying assignment. For a sunple example, consider F - x V -<y. The value of P is 1 for three assignments:

1. Ti(x) - 1; Ti(y) - 1.

2. Г2(а:) = 1;Т2(у)-0.

3. Гз(х)=0;Гз(у) = 0.

F has value 0 only for the fourth assignment, where x - 0 and у = 1. Thus, F is satisfiable. □

The satisfiability problem is:

Given a boolean expression, is it satisfiable?

We shall generally refer to the satisfiability problem as SAT. Stated as a language, the problem SAT is the set of (coded) boolean expressions that are satisfiable. Strings that either are not valid codes for a boolean expression or that are codes for an unsatisfiable boolean expression are not in SAT.

10.2.2 Representing SAT Instances

The symbols in a boolean expression are Л, V, , the left and right parentheses, and symbols representing variables. The satisfiabiUty of an expression does not depend on the names of the rariables, only on whether two occurrences of variables are the same variable or different variables. Thus, we may assume that the variables are Xi,X2,... , although in examples we shall continue to use variable names like у or z, as well as xs. We shall also assume that variables are renamed so we use the lowest possible subscripts for the variables. For instance, we would not use x unless we also used Xi through хц in the same expression.

Since there are an infinite number of symbols that could in principle, appear in a boolean cx])ression, we have a familiar problem of having to de\iHe a code with a fixed, finite alphabet to represent expressions with arbitrarily large numbers of variables. Oidy then can wo talk about SAT as a problem, that is. as a language over a fixed alphabet consisting of the codes for those boolean expressions that are satisfiable. The code we shall use is as follows:

1. The symbols Л, V, -, (, and ) are re])resented by themselves.

2. The variable x/ is represented by the synd)ol x followed by Os and Is that represent i in binary.

Thus, the alphabet for the S.AT problem/language has only eight symbols. .All instances of S.A.T are strings in this fixed, finite alphabet.

ExEunple 10.8 : Consider the expression x A -liy V г) from Example 10.6. Our first step in coding it is to replace the variables by subscripted хя. Since there are three variables, we must use xj. x-2, and x. We have freedom regarding which of X, 7/, and z is replaced by each of the Xis, and to be specific, let з; = 3-], у = X2, and z - x. Then the expression becomes X] Л -<(х-2 V агз). The code for this expression is:

:i-l Л -{xlO V xll)

□

Notice that the length of a coded boolean expression is approximately the same as the number of positions in the expression, counting each variable occurrence as 1. The reason for the difference is that if the expression has m positions, it can have 0(m) variables, so variables may take O(logm) symbols to code. Thus, an expression whose length is m po.4ition5 can have a code as long as -77- = C(mlogn7) symbols.

However, the difference between 777, and m logm is surely limited by a polynomial. Thns, as long as we only deal with the i.ssue of whether or not a problem can be solved in time that is polynomial in its input length, there is no need to distinguish between the length of an expressions code and the number of positions in the ex])ression itself

10.2.3 NP-Completeness of the SAT Problem

We now prove Cooks Theorem, the fact that SAT is NP-complete. To prove a problem is NP-c<miplete, we n{;(;d first to show that it is in NV. Then, we must show that every language in AV reduces to the problem in question. In general, we show tho ,S(!Cond part by offering a polynomial-time reduction from some other NP-comph;t<; problem, and then invoking Theorem 10.5. But right now, we dont know any NP-compiete problems to reduce to S.A.T. Thus, the only strat(!gy available is to reduce absolutely every problem in MV to SAT.

Theorem 10.9: (Cooks Theorem) SAT is NP-complete.