Figure 10,6: Pushing ->s down the expression tree so they appear only in literals

The second step is to write an expression that is the AND and OR of literals as a product of clauses; i.e., to put it in CNF. By introducing new variables, we eure able to perform this transformation in time that is a polynomial in the size of the given expression. The new expression F will not be equivalent to the old expression E, in general. However, F will be satisfiable if and only if E is. More specifically, if T is a truth assignment that makes E true, then there is an extension of T, say 5, that makes F true; we say S is an extension of T if S assigns the same value as T to each variable that T assigns, but S may also assign a value to variables that T does not mention.

Our first step is to push -is below As and Vs. The rules we need are:

1. A F) -i(E) V -i(F ). This rule, one of DeMorgans laws, allows us to push below Л. Note that as a side-effect, the A is changed to an V.

2. ->{E V F) -<(E) A -.{F). The other DeMorgans law pushes below V. The V is changed to A as a side-effect.

3. -i{{E)) E. This law of double negation cancels a pair of -is that apply to the same expression.

Example 10.11: Consider the expression E - - ((~{x + y)){x + y). Notice that we have used a mixture of our two notations, with the -i operator used explicitly when the expression to be negated is more than a single variable. Figure 10.6 shows the steps in which expression E has all its --s pushed down until they become parts of literals.

The final expression is equivalent to the original and is an OR-and-AND expression of literals. It may be further simplified to the expression x +y, but that simplification is not essential to our claim that every expression can be rewritten so the -is appear only in literals. □

Theorem 10.12: Every boolean expression E is equivalent to an expression F in which the only negations occur in literals; i.e., they apply directly to variables. Moreover, the length of F is linear in the number of symbols of E, and F can be constructed from E in polynomial time.

PROOF: The proof is an induction on the number of operators (Л, V, and -) in E. We show that there is an equivalent expression F with -Is only in literals. Additionally, if E has n>l operators, then F has no more than 2n -1 operators.

Since F need not have more than one pair of parentheses per operator, and the number of variables in an expression cannot exceed the number of operators by more than one, we conclude that the length of F is linearly proportional to the length of E. More importantly, we shall see that, because the construction of F is quite simple, the time it takes to construct F is proportional to its length, and therefore proportional to the length of E.

BASIS: If E has one operator, it must be of the form ->x, x V y, от x A y, for variables x and y. In each case, E is already in the required form, so F = E serves. Note that since E and F each have one operator, the relationship F has at most twice the number of operators of E, minus 1 holds.

INDUCTION: Suppose the statement is true for all expressions with fewer operators than E. If the highest operator of E is not -i, then E must be of the form El V E2 от El A E2. In either case, the inductive hypothesis applies to El and E2; it says that there are equivalent expressions Fi and F2, respectively, in which all -is occur in literals only. Then F = Fi V F2 от F = (Fi) A (F2) serves as a suitable equivalent for E. Let Ei and E2 have a and Ь operators, respectively. Then E has a-hb + 1 operators. By the inductive hypothesis, Fi and F2 have at most 2a - 1 and 26-1 operators, respectively. Thus, F has at most 2a H- 26 - 1 operators, which is no more than 2(a-i-b-bl)-l,or twice the number of operators of E, minus 1.

Now, consider the case where E is of the form -lEi. There are three cases, depending on what the top operator of Ei is. Note that £1 must have an operator, or E is really a basis case.

1. El = ->E2. Then by the law of double negation, E - -i(-iF2) is equivalent to E2. Since £2 has fewer operators than E, the inductive hypothesis applies. We can find an equivalent F for E2 in which the only -Is are in literals. F serves for E as well. Since the number of operators of F is at most twice the number in E2 minus 1, it is surely no more than twice the number of operators in E minus 1.

2. £1 = E2 V £3. By DeMorgans law, E = ->{E2 V £3) is equivalent to ((£2)) Л {- {Es)). Both -.{E2) and -(Ез) have fewer operators than E, so by the inductive hypothesis they have equivalents F2 and F3 that have -Is only in literals. Then F - (F2) A (F3) serves as such an equivalent for E. We also claim that the number of operators in F is not too great. Let E2 and E3 have a and b operators respectively. Then E has a-1-6-1-2 operators. Since -(F2) and -(£3) have a+1 and b+1 operators, respectively, and F2 гmd F3 are constructed from these expressions, by the inductive hypothesis we know that F2 and F3 have at most 2(a -Ы) - 1 and 2{6-l-1) -1 operators, respectively. Thus, F has 2a-b 26-t-3 operators

Descriptions of Algorithms

While formally, the running time of a reduction is the time it takes to execute on a single-tape Turing machine, these algorithms are needlessly complex. We know that the sets of problems that can be solved on conventional computers, on multitape TMs and on single tape TMs in some polynomial time are the same, although the degrees of the polynomials may differ. Thus, as we describe some fairly sophisticated algorithms that are needed to reduce one NP-complete problem to another, let us agree that times will be measured by efficient implementations on a conventional computer. That understanding will allow us to avoid details regarding manipulation of tapes and will let us emphasize the important algorithmic ideas.

at most. This number is exactly twice the number of operators of E, minus 1.

3. £ 1 = E2 Л E3. This argument, using the second of DeMorgans laws, is essentially the same as (2).

10.3.3 NP-Completeness of CSAT

Now, we need to take an expression E that is the AND and OR of literals and convert it to CNF. As we mentioned, in order to produce in polynomial time an expression F from E that is satisfiable if and only if E is satisfiable, we must forgo an equivalence-preserving transformation, and introduce some new variables for F that do not appear in E. We shall introduce this trick in the proof of the theorem that CSAT is NP-complete, and then give an example of the trick to make the construction clearer.

Theorem 10.13: CSAT is NP-complete.

PROOF: We show how to reduce SAT to CSAT in polynomial time. First, use the method of Theorem 10.12 to convert a given instance of SAT to an expression E whose --s are only in literals. We then show how to convert E to a CNF expression F in polynomial time and show that F is satisfiable if and only if S is. The construction of F is by an induction on the length of E. The particular property that F has is somewhat more than we need. Precisely, we show by induction on the number of symbol occurrences ( length ) E that:

There is a constant с such that if j& is a boolean expression of length n with -is appearing only in literals, then there is an expression F such that: