Polynomial-time converter

for m

Figure 10.5: If SAT is in V, then every language in AfV could be shown to be in P by a DTM designed in this manner

! Exercise 10.2.2: Suppose G is a graph of four nodes: 1, 2, 3, and 4. Let aij, for 1 < г < j < 4 be a propositional variable that we interpret as saying there is an edge between nodes i and j. Any graph on these four nodes can be represented by a truth assignment. For instance, the graph of Fig. 10.1 is represented by making xi4, false and the other Eve variables true. For any property of the graph that involves only the existence or nonexistence of edges, we can express that property as a boolean expression that is true if and only if the truth assignment to the variables describes a graph that has the property. Write expressions for the following properties:

* a) G has a Hamilton circuit.

b) G is connected.

c) G contains a clique of size 3, that is, a set of three nodes such that there is an edge between every two of them (i.e., a triangle in the graph).

d) G contains at least one isolated node, that is, a node with no edges.

10.3 A Restricted Satisfiability Problem

Our plan is to demonstrate a wide variety of problems, such as the TSP problem mentioned in Section 10.1.4, to be NP-complete. In principle, we do so by finding polynomial-time reductions from the problem SAT to each problem of interest. However, there is an important intermediate problem, called 3SAT, that is much easier than SAT to reduce to typical problems. 3SAT is still a problem about satisfiability of boolean expressions, but these expressions have a very regular form: they are the AND of clauses, each of which is the OR of exactly three variables or negated variables.

In this section we introduce some important terminology about boolean expressions. We then reduce satisfiability for any expression to satisfiabUity for expressions in the normed form for the 3SAT problem. It is interesting to observe that, while every boolean expression E has an equivalent expression F in the normal form of 3SAT, the size of F may be exponential in the size of

Conjunction is a fancy term for logical AND.

E. Thus, our polynomial-time reduction of SAT to 3SAT must be more subtle than simple boolean-algebra manipulation. We need to convert each expression E in SAT to another expression F in the normal form for 3SAT. Yet F is not necessarily equivalent to E. We can be sure only that F is satisfiable if and only if E is.

10.3.1 Normal Forms for Boolean Expressions

The following are three essential definitions:

A literal is either a variable, or a negated variable. Examples are x and ->y. To save space, we shall often use an overbar у in place of a literal such as -ly.

A clause is the logical OR of one or more literals. Examples are x,x\/ y, and xV у V z.

A boolean expression is said to be in conjunctive normal forrr? or CNF, if it is the AND of clauses.

To further compress the expressions we write, we shall adopt the alternative notation in which V is treated as a sum, using the 4- operator, and A is treated as a product. For products, we normally use juxtaposition, i.e., no operator, just as we do for concatenation in regular expressions. It is also then natural to refer to a clause as a sum of literals and a CNF expression as a product of clauses.

Example 10.10: The expression {x V ->y) A {-ix V z) will be written in our compressed notation as {x + y){x + z). It is in conjunctive normal form, since it is the AND (product) of the clauses [x + y) and ix + z).

Expression {x + yz){x-\-у-\- z)(y + z) is not in CNF. It is the AND of three subexpressions, [x + yz), [x + y + z], and (y 4- z). The last two are clauses, but the first is not; it is the sum of a literal and a product of two literals.

Expression xyz is in CNF, Remember that a clause can have only one literal. Thus, our expression is the product of three clauses, (i), (y), and (z), □

An expression is said to be in k-conjunctive normal form (ft-CNF) if it is the product of clauses, each of which is the sum of exactly к distinct hterals. For instance, {x + y)(y + z){z + x) is in 2-CNF, because each of its clauses has exactly two hterals.

All of these restrictions on boolean expressions give rise to their own problems about satisfiabiUty for expressions that meet the restriction. Thus, we shall speak of the following problems:

CSAT is the problem: given a boolean expression rn CNF, is it satisfiable?

Haadling Bad Input

Each of the problems we have discussed - SAT, CSAT, 3SAT, and so on - are languages over a fixed, 8-symbol alphabet, whose strings we sometimes may interpret as boolean expressions. A string that is not interpretable as an expression cannot be in the language SAT. Likewise, when we consider expressions of restricted form, a string that is a well-formed boolean expression, but not an expression of the required form, is never in the language. Thus, an algorithm that decides the CSAT problem, for example, will say no if it is given a boolean expression that is satisfiable, but not in CNF.

AS AT is the problem: given a boolean expression in fc-CNF, is it satisfiable?

We shall see that CSAT, 3SAT, and fcSAT for all к higher than 3 are NP-complete. However, there are linear-time algorithms for IS AT and 2SAT.

10.3.2 Converting Expressions to CNF

Two boolean expressions are said to be eguivalent if they have the same result on any truth assignment to their variables. If two expressions are equivalent, then surely either both are satisfiable or neither is. Thus, converting arbitrary expressions to equivalent CNF expressions is a promising approach to developing a polynomiaJ-time reduction from SAT to CSAT. That reduction would show CSAT to be NP-complete.

However, thmgs are not quite so simple. While we can convert any expression to CNF, the conversion can take more than polynomial time. In particular, it may exponentiate the length of the expression, and thus surely take exponential time to generate the output.

Fortunately, conversion of an arbitrary boolean expression to an expression in CNF is only one way that we might reduce SAT to CSAT, and thus prove CSAT is NP-complete. All we have to do is take a SAT instance E and convert it to a CSAT instance F such that F is satisfiable If and only if E is. It is not necessary that E and F be equivalent. It is not even necessary for E and F to have the same set of variables, and in feet, generally F will have a superset of the variables of E.

The reduction of SAT to CSAT will consist of two parts. First, we push ail -is down the expression tree so that the only negations are of variables; i.e., the boolean expression becomes an AND and OR of literals. This transformation produces an equivalent expression and takes time that is at most quadratic in the size of the expression. On a conventional computer, with a carefully designed data structure, it takes only linear time.