1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 61
Текст из файла (страница 61)
Hence this approach fails toestablish that either one of EQt:IVALENCE OF NONDETERMINISTIC FINITE AUTOMATA and EQUIVALENCE OF REGULAR EXPRESSIONS is in P -as do, in fact,far more sophisticated approaches.Problems for Section 6.26.2.1. Show that a graph is Eulerian if and only if it is connected and the indegree of each node equals its out-degree.
(Hint: One direction is easy.For the other, start at a node, and traverse an edge to get to another node.Continue traversing new edges until you cannot find a new one; at this pointyou are back at the starting node (why?). Show how you can start againand traverse the pieces of the graph you have left untraversed.)6.2.2. Prove that the algorithm given in the text solves PARTITION in O(nH)steps.6.2.3. Solve the traveling salesman problem for five cities A, B, C, D, and E withthe following diHtance matrix:BCD E~c ~ ~n6.2.4. We study optimization problems in terms of their language versions, definedin terms of a "budget" B or "target" K. Choose one of the optimizationproblems introduced in this section, and show that there is a polynomialalgorithm for the original problem if and only if there is one for the "yes-no"version.
(One direction is trivial. For the other, binary search is needed,plus a property of these problems that might be called self-reducibility.)288Chapter 6: COMPUTATIONAL COMPLEXITY'""'v)('-6.2.5. Does the undirected graph above have a Hamilton cycle? What is the largestclique, largest independent set, and smallest node cover of this graph?BBOOLEAN SATISFIABILITYIn the previous section we saw many interesting computational problems thatare in P, and some others that are suspected not to be in P. But perhaps themost fundamental problems of both kinds are related to Boolean logic.Boolean logic is a familiar mathematical notation for expressing compoundstatements such as "either it is not raining now or the cane is not in the corner."In Boolean Logic we use Boolean variables Xl, X2, ...
to stand for the individual statements such as "it is raining now." That is, each variable denotes astatement that can in principle be true or false independently of the truth valueof the others. We then use Boolean connectives to combine Boolean variablesand form more complicated Boolean formulae. For our purposes in this bookwe need only consider Boolean formulae of a specific kind, defined next.Definition 6.3.1: Let X = {Xl, X2, ... Xn} be a finite set of Boolean variables, and let X = {Xl, X2, ...
X,,}, where the Xl, X2, ... ,X" are new symbolsstanding for the negations, or opposites, of Xl, X2, ... ,X". 'Ve call the elements of X U X literals; variables are positive literals, whereas negationsof variables are negative literals. A clause C is a nonempty set of literals:C ~ Xu X. Finally, a Boolean formula in conjunctive normal form (or6.3: Boolean Satisfiability289simply Boolean formula, since we shall treat no other kind in this book) is aset of clauses defined on X.Example 6.3.1: Let X = {Xl,X2,X3}, and therefore X = {Xl,X2,Xs}.
C l ={Xl, X2, X3} is a clause. Although a clause is a set of literals, we shall employ aspecial notation when writing clauses: We shall use parentheses instead of ourusual set brackets; and we shall separate the various literals in the clause (if thereare more than one) by the delimiter V (pronounced or), instead of a comma.As always with sets, order is not important, and repetition of elements is nottolerated. For example, the clause C above will be written C = (Xl V X2 V X3).The following is a Boolean formula in conjunctive normal form:(1)It consists of three clauses, one of which is C above.<)Definition 6.3.2: So far we have only defined the syntax, or apparent structure,of Boolean formulae. We next define the semantics, or meaning, of such aformula. Let F be a Boolean formula in conjunctive normal form defined overthe variables in X = {Xl, X2, ...
x n }. A truth assignment for F is a mappingfrom X to the set {T, J.. }, where T and J.. are two new symbols pronouncedtrue and false, respectively. We say that a truth assignment T satisfies F ifthe following holds: For each clause C E F there is at least one variable Xi suchthat either (a) T(Xi) = T, and Xi E C, or (b) T(Xi) = J.., and Xi E C. That is,a clause is satisfied if it contains at least one true literal, where Xi is consideredtrue if and only if T(Xi) = T, and Xi is considered true if and only if T(Xi) = ...L.Finally, F is called satisfiable if there is a truth assignment that satisfiesit.Example 6.3.2: The Boolean formula F in (1) above is satisfied by the truthassignment T, where T(xd = J.., T(X2) = T, and T(X3) = T. This truthassignment satisfies the clause C 1 = (Xl V X2 V X3) because T(X3) = T, andX3 E C 1; T satisfies the clause C 2 = (xd because Xl E C 2, and T(xd = J..; andit finally satisfies the third clause C 3 = (X2 V X2) (this is not too surprising, asany truth assignment would satisfy C 3 ).
There are many truth assignments thatfail to satisfy F: For example, any truth assignment T' with T'(xt) = J.. wouldfail to satisfy C 2 and thus fail to satisfy F. Still, F is satisfiable, because thereis at least one truth assignment that satisfies it.<)Example 6.3.3: Consider now this formula:290Chapter 6: COMPUTATIONAL COMPLEXITYIs it satisfiable? The correct answer here is "no." Let us prove it.The clause (Xl V X2 V X3) requires that at least one of the variables Xl, X2,and X3 be T. Similarly, the last clause requires that at least one of them be .1.Consider then the remaining three clauses, and suppose that T(xt) = T.
Thenin order for the clause (Xl V X2) to be satisfied, T(X2) must be T; and to satisfy(X2 V X3) we must have T(X3) = T. On the other hand, if T(xt) = .1 thenthe (X3 V xt) clause forces T(X3) to be .1, and the (X2 V X3) clause then makesT(xz) necessarily .i. So, no matter what T(Xl) is, the truth values of the threevariables must be the same if the formula is to be satisfied.To summarize, for a truth assignment to satisfy pi it must (a) map atleast one variable to T; (b) map at least one variable to .1; and (c) map allthree variables to the same truth value. This is clearly impossible, and thus piencodes a contradiction: It is unsatisfiable.<)This suggests the following important problem:SATISFIABILITY:Given a Boolean formula F in conjunctive normal form, isit satisfiable?As it perhaps became apparent in the previous example, it is a fairly trickyproblem.
Indeed, there is no known polynomial-time algorithm to date for thisfundamental and very well-studied problem, and it is widely believed that nosuch algorithm exists.2-SATISFIABILITYSuppose that we restrict the instances of SATISFIABILITY to ones in which allclauses have two or fewer literals. What results is a new problem, which we call2-SATISFIABILITY. We say that 2-SATISFIABILITY is a special case of SATISFIABILITY. By this we mean that the set of all possible inputs is a subset of the setof inputs for SATISFIABILITY, and the answers to each common input in the twoproblems are the same. A typical instance of 2-SATISFIARILITY is shown below.We shall next describe a sensible method for searching for a satisfying truth assignment for such a formula.
During the course of our method, several variableswill have been assigned T or .1, while the rest are not yet assigned. Initially novariable is assigned a truth value.Suppose that there is in our formula a clause with just one literal, say thethird clause (xd in the example in (2).
Then clearly this literal must be Tin any satisfying truth assignment, and therefore we can immediately decideon the value of this variable. That is, in our example we immediately decide6.3: Boolean Satisfiability291that T(xt) = T, and proceed. Now that we know that T(xt) = T, we can omitfrom the formula all clauses that contain Xl as one of their literals, because theseclauses are already satisfied (in our example we omit the first clause).
If howevera clause contains the opposite literal Xl, then we omit the literal from the clause,because this literal is ..1 and thus it is of no use in satisfying the clause. In ourexample, the first clause is omitted, and the fourth clause is replaced by (X2).Thus, assigning a truth value to a literal that appears alone in a clause, mayresult in new single-literal clauses, and we must repeat (in our example (2) wenext set T(X2) = ..i).We call this process of pursuing one-literal clauses until none exists a purge.If at any point of the purge the empty clause is produced -presumably becauseboth clauses (Xi) and (Xi), for some i, were present at the previous step- thenwe say that the purge has failed.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
