1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 65
Текст из файла (страница 65)
Denote by 1f(i)the unique j for which T(Xi.rr(il) = T.The set of clauses in (1) above must also be satisfied. This means thatwhenever i = 1f(j) and k = 1f(j + 1) (where again n + 1 means 1) then (j,k)must be an edge of G. It follows that (1f(1), 1f(2), ...
, 1f(n)) is indeed a Hamiltoncycle of G. The if direction has been proved.Conversely, suppose that G has a Hamilton cycle, say (1f(1), 1f(2), ... , 1f(n)).Then it is easy to see that the truth assignment T, where T(Xij) = T if and onlyif j = 1f( i), satisfies all clauses of T( G), and the proof is complete.Later in this chapter we shall see a reduction in the opposite direction (Theorems 7.3.1 and 7.3.2).Correctly interpreting polynomial reductions as to the information theyreveal with respect to the difficulty of the problems involved can be confusing,and requires some care and experience.
The reader is encouraged at this pointto ponder these issues: Is this reduction good news or bad news about thecomplexity of HAMILTON CYCLE? of SATISFIABILITY? Suppose that we have apolynomial-time algorithm for HAMILTON CYCLE; what can we conclude aboutSATISFIABILITY in the light of this reduction? What if we had a polynomialtime algorithm for SATISFIABILITY? What can we conclude if we know thatHAMILTON CYCLE is a difficult problem? that SATISFTABTLITY is a difficultproblem"? <;7.1: Polynomial-time Reductions305Example 7.1.2: You must schedule n tasks on two machines. Both machineshave the same speed, each task can be executed on either machine, and thereare no restrictions on the order in which the tasks have to be executed.
You aregiven the execution times aI, ... ,an of the tasks and a deadline D, all in binary.Can you complete all these tasks on the two machines within this deadline?Another way to state this question is the following: Is there a way to partition the given binary numbers into two sets so that the numbers in each set addup to D or less? We call this problem, whose relation to the PARTITION problem defined in the last chapter is perhaps clear, TWO-MACHINE SCHEDULING.We also introduce another problem, also closely related to PARTITION:KNAPSACK: Given a set S = {a1, ... , an} of nonnegative integers, and aninteger K, all represented in binary, is there a subset P ~ S such thatI::aiEP ai = K?(This graphic name is supposed to bring to mind a hiker who is trying to fill herknapsack to its limit with items of varying weights.)How are these three problems (PARTITION, KNAPSACK, and TWO-MACHINESCHEDULING) related by polynomial reductions? We shall show that there aresix polynomial reductions, reducing anyone of these three problems to any other!Suppose that we have an instance of KNAPSACK, with integers aI, ...
,anand K; we must reduce it to an equivalent instance of PARTITION. If K happensto be equal to H = ~ I::7=1 ai, the half-sum of the given integers, then all ourreduction has to do is to erase K from the input: The resulting instance ofpartition is equivalent to the given instance of KNAPSACK. The problem is, ofcourse, that K will not in general be equal to H. But this is easy to fix: Addto the set of ai's two large new integers a n+1 = 2H + 2K and a n +2 = 4H(notice that these numbers are integers even if H fails to be one).
Consider nowthe resulting set of integers {a1, .. . ,an +2} as an instance of PARTITION -thereduction is complete. It is obvious that this reduction can be carried out inpolynomial time.We must now show that the reduction works; that is, that the instance ofpartition has a solution if and only if the original instance of knapsack had one.Notice first that if the new set of integers can be partitioned into two sets withequal sums, then the two new integers a n +1 and a n +2 must be on opposite sidesof the partition (their sum exceeds that of the remaining integers).
Let P bethe set of integers among the original ones aI, ... ,an that are on the same sideas a,,+2 = 4H. We have that4H+2: ai = 2H + 2K + 2:aiEPa,ES-Pai·306Chapter 7: NP-COMPLETENESSAddingLaiEPai to both sides, we get (since4H+2LaiESai =2H)2: ai = 4H + 2K,aiEPor LaiEP ai = K. Hence, if the resulting instance of PARTITION has a solution,then the original instance of KNAPSACK has one.
And conversely, if we have asolution of KNAPSACK, then adding a n +2 to it yields a solution of the instanceof PARTITION.This was the reduction from KNAPSACK to PARTITION. We started withan arbitrary instance of KNAPSACK and constructed an equivalent instance ofPARTITION. A reduction in the opposite direction is trivial, because PARTITIONis a special case of KNAPSACK.
Given any instance of PARTITION with integers al, ... ,an, the reduction to KNAPSACK transforms the given instance ofPARTITION to the instance of KNAPSACK with the same numbers, and bound1 ",nI, = 2" L...i=l ai·But what if K is not an integer (that is, the given integers add to an oddnumber)? Then we can have the reduction produce any impossible instance ofKNAPSACK we wish, such as the one with n = 1, al = 2, and K = 1 -the givenip.stance of PARTITION was also impossible.The reduction from PARTITION to TWO-MACHINE SCHEDULING is also easy:Given an instance of PARTITION with integers al, ... , an, the reduction produces an instance of TWO-MACHINE SCHEDULING with n tasks, execution timesaI, ...
, an, and deadline D = l ~ L~=l ad (if ~ L~= 1 ai is not an integer, thenthis is already an impossible instance). It is easy to see that the resulting instanceof TWO-MACHINE SCHEDULING is solvable if and only if the original instance ofPARTITION was. This is because the tasks can be partitioned into two sets withsums at most D if and only if they can be partitioned into two sets with sumsexactly D.,r}-.~--------------- D--------------------~·-Machine 1",)I~;...."..!; ..... .Machine 2Figure 7-2The reduction from TWO-MACHINE SCHEDULING to PARTITION is a little more involved.
Suppose that we are given an instance of TWO-MACHINESCHEDULING with task lengths aI, ... ,an, and deadline D. Consider the number I = 2D - L~=l ai. Intuitively, I is the total idle time in any legal schedule7.1: Polynomial-time Reductions307(see Figure 7-3). 1t is the amount of slack that we have in solving the schedulingproblem. We add now several new numbers to the set of lengths of tasks, suchthat (a) the sum of these new numbers is I; and (b) moreover, we can make upany sum between 0 and I by adding a subset of these new numbers. It is nothard to see that, if we were able to do this, the resulting instance of PARTITIONwould be equivalent to the original instance of TWO-MACHINE SCHEDULING, because we could then transform any feasible schedule of the original ta.sks into anequitable partition of the new set of numbers by adding to each of the two setsa subset of the newly introduced numbers that will bring the sum of both to D.All we ha\'e to do now is supply integers, adding up to I, so that any numberbetween zero and I is the sum of a set of these numbers.
Superficially, this lookstrivial to do: Add I copies of the integer 1. What is wrong with this reduction,however, is that it is not a polynomial-time reduction, for the sanle reason forwhich the algorithm for PARTITION we sketched in the previous chapter failed tobe polynomial: The integer I is not bounded by a polynomial in the size of theinput -since the input consists of the task lengths and the deadline, all encodedin binary, the number I could be exponentially large in the size of the input.The solution is a little more complicated: The numbers we add are allpowers of 2 that are smaller than ~I, plus another integer to bring the sum to I.For example, if 1= 56, then the n~wly added integers would be 1,2,4,8,16, and25.
All integers bdween 0 and 56, and only these, can be made up as the sumof some subset of these integers. This completes the description of the reductionfrom TWO-MACHINE SCHEDULING to PARTITION; the reduction is polynomial,because the number of integers we introduce is bounded by the logarithm of I-which is less than the size of the input.\>In the above example we did not discuss direct reductions from KNAPSACKto TWO-MACHINE SCHEDULING and back. But there is no need: As we shownext, polynomial reductions compose in a transitive fashion.
Recall that thecomposition of two functions f : A I--t Band 9 : B I--t C is the function fog :A I--t C, where for all x E A, f 0 g(x) = g(f(x)).Lemma 7.1.1: If 71 is a polynomial reduction from L1 to L2 and 72 is a polynomial reduction from L2 to L 3 , then their' composition 71 072 is a polynomialreduction from Ll to L 3 •Proof: Suppose that 71 is computed by a Turing machine Ml in time PI, apolynomial, and 72 is computed by M2 in time P2.
also a polynomial. Then71 072 can be computed by the machine Jl,h M 2 . On input x E I:i, Ml M2 willoutput 71 0 72 (x) in time bounded by pdlxl) + P2(PI (Ixl)) -a polynomial. Thelatter term reflects the fact that 171(X)1 cannot be larger than Pl(lxl).It remains to show that x E Ll if and only if 71 0 72 (x) E L 3 • But this istrivial: x E L1 if and only if 71 (x) E L 2 , if iUld only if 71 0 72 (x) E L 3 . •Chapter 7: NP-COMPLETENESS308We finally arrive at the following important definition.Definition 7.1.2: A language L ~ ~* is called NP-complete if(a) L E NP; and(b) for every language L' E NP, there is a polynomial reduction from L' to L.Just as the decidability of H captured the whole question of the decidabilityof Turing-acceptable languages, so the question of whether anyone NP-completelanguage is in P turns out to be equivalent to the whole P = NP question:Theorem 7.1.1: Let L be an NP-complete language.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
