1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 60
Текст из файла (страница 60)
Naturally, thefollowing algorithm does solve the problem:Examine all possible permutations of the nodes;for each test whether it is a Hamilton cycle.Unfortunately it fails to be polynomial, as do all simple ways of improvingit and speeding it up.Optimization ProblemsThe TRAVELING SALESMAN PROBLEM, introduced informally in the beginningof this chapter, is another simply stated problem for which, despite intenseresearch efforts over several decades, no polynomial-time algorithm is known.We are given a set {Cl' C2, ...
, cn } of cities, and an n x n matrix of nonnegativeintegers d, where d;j denotes the distance between city Ci and city Cj. We areassuming that d;i = 0 and dij = d ji for all i,j. We are asked to find the shortest6.2: Problems, problems ...283tour of the cities, that is, a bijection 7r from the set {I, 2, ... , n} to itself (where7r( i) is, intuitively, the city visited ith in the tour), such that the quantityc(7r)= d7r (1)7r(2) + d7r (2)7r(3) + ... + d7r (n-l)7r(n) + d7r (n)7r(l)is as small as possible.There is a serious obstacle for studying the traveling salesman problemwithin our framework of problems and languages: Unlike all other problems wehave seen in this chapter, the traveling salesman problem is not the kind ofproblem that requires a "yes" or "no" answer and can therefore be studied interms of a language.
It is an optimization problem, in that it requires us to findthe best (according to some cost function) among many possible solutions.There is a useful general method for turning optimization problems intolanguages, so that we can study their complexity: Supply each input with abound on the cost function. In this case, consider the following problem:Given an integer n 2 2, an n x n distancematrix d ij , and an integer B 2 0 (intuitively, the budget of the travelingsalesman) find a permutation 7r of {I, 2, ... , n} such that c(7r) ::; B.TRAVELING SALESMAN PROBLEM:If we could solve the original optimization problem in polynomial time, that is, ifwe had an algorithm for computing the cheapest tour, then obviously we wouldbe able to solve this "budget" version in polynomial time as well: Just computethe cost of the cheapest tour and compare it with B.
Thus, any negative resultabout the complexity of the TRAVELING SALESMAN PROBLEM as defined justnow will reflect negatively on our prospects for solving the original, optimizationversion of the problem.We shall use this maneuver to bring many interesting optimization problemswithin our language framework. In the case of maximization problems we do notsupply a budget B but instead a goal K. For example, the following is animportant maximization problem transformed this way:INDEPENDENT SET: Given an undirected graph G and an integer K 2 2, isthere a subset C of V with 101 2 K such that for all Vi, Vj E C, there is noedge between Vi and Vj?is yet another natural and simply stated problem for which,despite prolonged and intense interest by researchers, no polynomial-time algorithm has been found.Let us introduce two more optimization problems on undirected graphs.The next problem is in some sense the exact opposite of INDEPENDENT SET:INDEPENDENT SETCLIQUE: Given an undirected graph G and an integer K 2 2, is there asubset C of V with 101 2 K such that for all Vi, Vj E C, there is an edgebetween Vi and Vj?Chapter 6: COMPUTATIONAL COMPLEXITY284For the next problem, let us say that a set of nodes covers an edge if itcontains at least one endpoint of the edge.NODE COVER: Given an undirected graph G and an integer B 2 2, is therea subset C of V with 101 ::; B such that C covers all edges of G?We can think of the nodes of an undirected graph as the rooms of a museum,and each edge as a long straight corridor that joins two rooms.
Then the NODECOVER problem may be useful in assigning as few as possible guards to therooms, so that all corridors can be seen by a guard.To illustrate these interesting problems, the largest independent set of thegraph in Figure 6-2 has three nodes; the largest clique has four nodes; andthe smallest node cover has six nodes. Can you find them? Can you convinceyourself that they are optimal?Figure 6-2Integer PartitionsSuppose that we are given several positive integers, say 38,17,52,61,21,88,25.We are asked whether they can be divided into two disjoint sets, which includebetween them all numbers, and both add up to the same number.
In the above6.2: Problems, problems ...example the answer is "yes," because 38The general problem is this:285+ 52 + 61 = 17 + 21 + 88 + 25 = 151.Given a set n nonnegative integers al, ... , an represented inbinary, is there a subset P ~ {I, ... , n} such that LiEP ai = Lilt P ai?PARTITION:This problem can be solved by a simple algorithm explained next. First, let Hbe the sum of all integers in S divided by 2 (if this number is not an integer,then the numbers in S add up to an odd number and cannot be partitioned intotwo equal sums; so we can already answer "no"). For each i, ~ i ~ n, definethis set of numbers:°B(i) = {b S H : b is the sum of some subset of the numbers{al, ... , ain.If we knew B(n), we could solve the PARTITION problem easily by just testingwhether H E B(n).
If so, there is a partial sum that adds up to H and theanswer is "yes"; otherwise, the answer is "no."But notice that B(n) can be computed by the following algorithm:B(O) := {a}.for i = 1,2, ... , n doB(i) := B(i - 1),for j = ai, ai + 1, ai + 2, ... , H doif j - ai E B(i - 1) then add j to B(i)For example, in the instance of PARTITION shown above, with al = 38, a2 = 17,a3 = 52, a4 = 61, a5 = 21, a6 = 88, a7 = 25, the B(i) sets are as follows:B(O) ={O}B(l) ={O, 38}B(2) ={O, 17, 38, 55}B(3) ={O, 17,38,52,55,69,90, 107}B(4) ={O, 17,38,52,55,61,69,78,90,107,113,116,130, 151}B(5) ={0,17,21,38,52,55,59,61,69, 73,76, 78,82,90,99,107,111,113,116,128,130, 134, 137, 151}B(6) ={O, 17, 21, 38, 52, 55, 59, 61, 69, 73, 76, 78, 82, 88, 90, 99,105,107,109,111,113,116,126,128,130,134,137,140,143,147, 149, 151}B(7) ={O, 17,21,25,38,42,46, 52, 55,59,61,63,69, 73, 76, 77,78,80,82,84,86,88,90,94,98,99,101,103,105,107,109,111,113,115,116,124,126,128,130, 132,134, 136,137, 138, 140, 141, 143, 147, 149,151}This instance of PARTITION is a "yes" instance, because the half-sum H = 151is contained in B(7).286Chapter 6: COMPUTATIONAL COMPLEXITYIt is easy to prove by induction on i that this algorithm correctly computesB(i), for i = 0, ...
, n, and does so in O(nH) time (see Problem 6.2.5). Have wethen proved that PARTITION is in P?The bound O(nH), despite its perfectly polynomial appearance, is not polynomial in the length of the input. The reason is that the integers aI, ... ,an aregiven in binary, and thus their sum will in general be exponentially large whencompared to the length of the input. For example, if all n integers in an instanceof PARTITION are about 2n , then H is approximately ~ 2n , while the length ofthe input is only O(n 2 ). In fact, PARTITION is one of the notoriously hardproblems, including the TRAVELING SALESMAN PROBLEM, HAMILTON CYCLE,and INDEPENDENT SET, for which no true polynomial algorithm is known orexpected any time soon (and which are the subject of the next chapter).However, the above algorithm does establish that the following problem isindeed in P.Given a set of n natural numbers {al, ...
, an} represented in unary, is there a subset P <;;;; {I, ... , n} such that LiEP ai =Liltpai?UNARY PARTITION:This is because the input of the unary version has length about H, and so theO(nH) algorithm suddenly becomes "efficient."This pair of problems, PARTITION and UNARY PARTITION, with their contrasting complexity, illustrates the following important fact about input representations: The precise representation of mathematical objects such as graphs,automata, Turing machines, and so on, as inputs to problems makes little difference in the membership of the corresponding language in P, because the lengthsof all reasonable representations of the same object are related by a polynomial.The only encoding convention whose violation leads to misleading results, is thatintegers should be encoded in binary, t and not in unary.Equivalence of Finite AutomataIn Chapter 2 we saw that the following important problem concerning finiteautomata is in P (Theorem 2.6.1, part (e)):Given two deterL(M2)?EQUIVALENCE OF DETERMINISTIC FINITE AUTOMATA:ministic finite automata Ml and M 2, is L(Md=In contrast, we noticed that we only know how to test nondeterministic finiteautomata for equivalence in exponential time.
That is, we do not know whethereither of the following two problems is in P:tOr in decimal, hexadecimal, or in any other radix system; all such representationsof the same integer have lengths that are constant multiples of each other.2876.2: Problems, problems ...EQUIVALENCE OF NONDETERMINISTIC FINITE AUTOMATA: Given two nondeterministic finite automata Ml and M 2, is L(Md = L(M2)?andEQUIVALENCE OF REGULAR EXPRESSIONS:Given two regular expressionsRl and R 2, is L(Rl) = L(R2)?One could solve either problem by transforming the two given nondeterministic automata (or regular expressions) to deterministic ones (Theorem 2.6.1),and then checking the resulting deterministic automata for equivalence. Theproblem is, of course, that the transformation from regular expressions or nondeterministic automata to deterministic may increase exponentially the numberof states of the automaton (recall Example 2.5.4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
