1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 68
Текст из файла (страница 68)
Show that (i) BINARY BOUNDEDTILING is in NEXP, and (ii) all languages in NEXP are polynomiallyreducible to nINARY BOUNDED TILING. That is to say, BINARY BOUNDEDTILING could be termed NEXP-complete.7.2.3. (a) Show that SATISFIABILITY remains NP-complete even if it is restrictedto instances in which each variable appears at most three times. (Hint:Replace the occurrences of variable, say, x, by new variables Xl, ... , X k.Then add a formula in which each of these variables appears twice, statingthat "all these variables are equivalent.")(b) What happens if each variable appears at most twice?7.2.4. Recall from Problem 6.4.3 that the class Np is closed under nonerasinghomomorphisms.
Show that P is closed under nonerasing homomorphismsif and only if P = NP. (Hint: One direction follows from (a). For theother, consider the following language, which is obviously in P:L = {xy : X E {O, I} * is the encoding of a Boolean formula F,and y E {T,.l}* is a truth assignment that satisfies F}.)7.2.5. Consider the following special case of MAX SAT:MAX 2-SAT: Given a set F of clauses, with at most two literals each, andan integer K, is there a truth assignment that satisfies at least K of theclauses?7.3: More NP-complete Problems317Show that MAX 2-SAT is NP-complete. (This is hard. Consider the clauses(x), (y), (z), (w), (xVy) , (fiVz) , (zVx), (xVw), (yVw), (zVw).
Show that thisset of ten clauses has the following property: All satisfying truth assignmenton x, y, z can be extended to satisfy seven clauses and no more, except forone, which can only be extended to satisfy six. Can you use this "gadget"to reduce 3-SATISFIABlLITY to MAX 2-SAT?)liiJMORE NP-COMPLETE PROBLEMSOnce we have proved our first NP-complete problem, we can reduce it to otherproblems, and those to still others, proving them all NP-complete.
See Figure7-4 for a depiction of the reductions proved in this section and the last, and seethe problems and the references for many more NP-complete problems.BOUNDED TILINGSATISFIABILITY3SAT~----INEQUIV ALENCE OF *-FREEINDEPENDENT SETMAXSATREGULAR EXPRESSIONSEXACT COVER/HAMILTON CYCLE~CLIQUENODE COVERKNAPSACK/UNDIRECTED HAMILTON CYCLEPARTITIONTWO MACHINESCHEDULINGTRA VELING SALESMAN PROBLEMFigure 7-4NP-complete problems arise in all fields and applications in which sophisticated computation is done. It is an important skill to be able to spotNP-complete problems -either by recognizing them as known NP-completeproblems,t or by proving them NP-complete from scratch.
Such knowledgetThis is not always easy, because NP-complete problems tend to come up in applications under all sorts of confusing guises.Chapter 7: NP-COMPLETENESS318saves researchers and programmers from futile attempts at impossible goals,and redirects their efforts to more hopeful venues (reviewed in Section 7.4 oncoping with NP-completeness). NP-complete problems such as GRAPH COLORING (see Problem 7.1.1), SATISFIABILlTY, and INDEPENDENT SET are importantbecause they come up frequently, and under various guises, in applications. Others, like the TRAVELING SALESMAN PROBLEM, are important not only becauseof their practical applications, but because they have been studied so much.
Stillothers, such as the problem we introduce next, are important because they areoften handy starting points for NP-cornpleteness reductions (SATISFIABILITY isimportant for all three reasons).We are given a finite set U = {u[, ... , un} (the universe), and a family ofmsubsets of U, F = {51"'" 5 m }. We are asked whether there is an exact cover,that is, subfamily C ~ F such that that the sets in C are disjoint and have U astheir union. We call this problem EXACT COVER.}or example, let the universe be U = {U[,U2,U3,U4,U5,U6} and the familyof subsets F = {{U[,U3},{U2,U3,U6},{U[,U5},{U2,U3,U4},{U5,U6},{U2,U4}}'An exact cover exists in this instance: It is C = { { U[, ud, {U5, U6}, {U2, u.t} }.Theorem 7.3.1: EXACT COVER is NP-complete.Proof: It is clear that EXACT COVER is Np: Given an instance (U, F) of theproblem, the subfamily sought is a valid certificate.
The certificate is polynomially concise in the size of the instance (since it is a subset of F, which is apart of the input), and it can be checked in polynomial time whether indeed allelements of U appear exactly once in the sets of C.To prove NP-completeness, we shall reduce SATISFIABILlTY to the EXACT COVER problem. That is, we are given a Boolean formula F with clauses{CI , ... , Ct} over the Boolean variables Xl, ... , X n , and we must show how toconstruct in polynomial time an equivalent instance T(F) of the EXACT COVERproblem. We shall denote the literals of clause Cj by Ajk, k = 1, ...
, mj, wherem j is the number of literals in Cj .The universe of T(F) is the setU={Xi:1 ~i ~n}U{Cj:j= 1, ... ,£}U{Pjk: 1 ~j~£,k= 1, ... ,mj}.That is, there is one element for each Boolean variable, one for each clause, andalso one element for each position in each clause.Now for the sets in :F. First, for each element Pjk, we have in F a set {pjd.That is to say, the Pjk'S are very easy to cover. The difficulty lies in coveringthe elements corresponding to the Boolean variables and clauses. Each variableXi belongs to two sets in F, namely, the setTi,T= {x;} U {Pjk: Ajk= x,},7.3: More NP-complete Problems319which also contains all negative occurrences of Xi, andwith the positive occurrences (notice the reversal in signs).
Finally, each clauseCi belongs to mj sets, one for each literal in it, namely {Cj , pjd, k = 1, ... , mj.These are all the sets in F, and this completes the description of T(F).Let us illustrate the reduction for the given Boolean formula F, with clausesCI = (Xl VX2), C2 = (Xl VX2 VX3), C3 = (X2), and C4 = (X2 VX3). The universeof T(F) isand t.he family of sets F consists of these sets:{PII}, {PI2}, {P21}, {P22}, {P23}, {P31,}{P41},{P42},TI,l..
= {XI,Pll},TI,T = {XI,P2d,T2,l.. = {X2,P22,P3d,T2,T = {X2,PI2,P4d,T 3,l.. = {X3,P23},T 3,T = {X2,P42},{CI,Pll}, {CI,PI2}, {C2,P2d, {C2,P22},{C2,P23}, {C3,P31,}, {C4,P41}, {C4,P42}.We claim that T(F) has an exact cover if and only if F is satisfiable.
Supposethat an exact cover C exists. Since each Xi must be covered, exactly one of thetwo sets T i ,T and Ti,l.. containing Xi must be in C. Think of Ti, T E C as meaningthat T(Xi) = T, and Ti,l.. E C as meaning that. T(Xi) = ..l; t.his defines a truthassignment T. We claim that T satisfies F. In proof, consider a clause Cj . Theelement in U corresponding to this clause must be covered by a set {Cj,pjd,for 1 :::; k :::; mj.
This means that the element pjk is not cont.ained in any otherset in the exact cover C; in particular, it is not in the set in C that contains thevariable that occurs (negated or not) at the kth literal of Cj . But this meansthat T makes the kth literal of Cj T, and thus Cj is satisfied by T. Hence F issatisfiable.Conversely, suppose that there is a truth assignment T that satisfies F. Wethen construct the following exact cover C: For each Xi, C contains the set T i , Tif T(Xi) = T, and it contains the set Ti,l..
if T(Xi) = ..l. Also, for each clause Cj ,C contains a set {Cj,pjd such that the kth literal of C j is made T by T, andthus Pjk is not contained in any set selected in C so far -we know that such a k320Chapter 7: NP-COMPLETENESSexists by our assumption that T satisfies F. Finally, having covered all Xi'S andC/s, C includes enough singleton sets to cover any remaining Pjk elements thatare not covered by the other sets.
In the illustration above, the exact cover thatcorresponds to the satisfying truth assignment T(xJ) = T, T(:r2) = T, T(:r3) =..l contains these sets: TI,T, T 2,T, T 3,J.., {CI,Pll}, {C2,P22}' {C3,P3d, {C4,P42},plus the singletons {PI2}, {p2d, {P23}, {p4d. We conclude that T(F) has an exactcover, and the proof is complete . •The Traveling Salesman ProblemWe can use the EXACT COVER problem to establish the NP-completeness ofHAMILTON CYCLE.Theorem 7.3.2: HAMILTON CYCLE is NP-complete.Proof: We already know that it is NP.
We shall now show how to reduce EXACTCOVER to HAMILTON CYCLE. We shall describe a polynomial-time algorithmwhich, given an instance (U, F) of EXACT COVER, produces a directed graphG = T(U, F) such that G has a Hamilton cycle if and only if (U, F) has an exactcover.The construction is based on a certain simple graph that has interestingproperties vis vis the Hamilton cycle problem -in NP-completeness jargonsuch graphs are called gadgets. Figure 7-5(a) shows this gadget. Imagine thatit is a part of a larger graph G, connected to the rest of G via the four nodesshown as solid dots. In other words, there are other nodes and edges to thegraph, but no edges other than the ones shown are adjacent to the three nodesin the middle.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
