The Efficiency Of Algorithms

	Скачать реферат: The Efficiency Of Algorithms

Some mathematical problems can be solved only by methods too slow for even the fastest computers. More efficient methods have not been found, but neither has it been proved, that there are no better methods by Harry R.Lewis and Christos H. Paradimitrou

Suppose you were asked to plan an itinerary for a traveling salesman who must visit a number of cities. You are given a map on which the distances between the cities are marked and you are asked to find the shortest route that passes through all the cities and returns to the starting point. An approach to this problem that is certain to give the correct answer is to trace all the possible routes, measure their length and pick the shortest one. If the tour included more than a few cities, however, hundreds or thousands of routes would have to be checked. If there were 100 cities, then even the fastest computers would require weeks of calculation to find the shortest path.

In the search for a quicker solution you might try some less rigorous methods. One idea that seems reasonable is always to visit nearby cities before going on to those farther away. You would soon discover, however, that this procedure does not invariably yield the correct answer. Other shortcuts also fail. In fact, the best methods known for solving the problem are not much better than the obvious but laborious procedure of checking all the possible itineraries. Mathematicians now suspect that this problem and many others like it may forever remain beyond our ability to solve in any efficient way. That speculation itself, however, is unconfirmed; although no faster methods of solution have been found, neither has it been proved that faster methods do not exist.

In the problem of the traveling salesman's tour it is not the solution for a particular set of cities that is of the greatest importance but a general method for finding the solution for any cities. Such a method is called an algorithm: it is a precisely stated procedure or set of instructions that can be applied in the same way to all instances of a problem. If the problem is to be solved with the aid of a computer, an algorithm is indispensable, because only those procedures that can be stated in the explicit and unambiguous form of an algorithm can be presented to a computer. Instructions that are vague or that rely on intuition are unacceptable.

An example of an algorithm is the procedure taught in the schools for the subtraction of whole numbers. If each of the steps in this procedure is applied correctly one at a time, the algorithm will always yield the correct result. What is more, once the algorithm has been learned or stored in the memory of a computer or embodied in the circuitry of an electronic calculator, it can be applied to an infinite set of subtraction problems. With this one algorithm the difference between any two whole numbers can be determined.

In principle any problem for which an algorithm can be devised can be solved mechanically. It may therefore seem surprising that there are problems for which algorithms exist but for which we so far have no practical general solution. The algorithms for solving these problems always give a correct answer, but they often require an inordinate amount of time. The problem of the traveling salesman's tour is among these intractable tasks.

The efficiency of computer algorithms is a topic of obvious practical importance. It is also of interest in more formal areas of mathematics. There are some problems in mathematics and logic for which no algorithm can ever be written, and there are many others for which efficient, fast algorithms are already known. Between these two groups is a third class of problems that can always be solved in principle, but for which there are only inefficient (and therefore largely unusable) algorithms. For some of these difficult problems mathematicians have been able to demonstrate that efficient algorithms can never be designed. For many of the most important problems, however, there is only the suspicion that good algorithms are impossible.

A given problem can have more than one algorithm for its solution. For example, children in Europe learn a procedure for subtraction slightly different from the one taught in the U.S. Both of the subtraction algorithms, however, give the same result in the same amount of time. That is not invariably the case with different algorithms for solving the same problem. One celebrated problem that can be solved by either a "fast" algorithm or a "slow" one is the problem of the Koenigsberg bridges.

In the I8th-century German city of Koenigsberg (which is now the Russian city of Kaliningrad) a park was built on the banks of the river Pregel and on two islands in the river. Within the park seven bridges connected the islands and the riverbanks. A popular puzzle of the time asked if it was possible to walk through the park by a route that crossed each of the bridges once and only once.

For the solution of the problem the size and shape of the islands and the length of the bridges are immaterial: the only essential information is the pattern of interconnections. This information can be presented compactly in the mathematical structure known as a graph, which is merely a set of points with lines drawn to join them. In the case of the Koenigsberg park each of the riverbanks, and each of the islands is condensed to a single point, and each of the bridges is represented by a line between two points. Thus the graph consists of four points and seven lines. If the lines are labeled, any path through the park can be specified by a simple listing of labels.

The obvious approach to the problem is to list all the paths that cross all the bridges and to eliminate from consideration those that cross any bridge more than once. This is the technique of exhaustive search, similar to the one employed in the problem of the traveling salesman. When the mathematician Leonard Euler was presented with the problem of the Koenigsberg bridges, he recognized the limitations of the technique and found another method. In recognition of his contribution a path that traverses each line of a graph exactly once is now called an Eulerian path.

Euler wrote: "The particular problem of the seven bridges of Koenigsberg could be solved by carefully tabulating all possible paths, thereby ascertaining by inspection which of them, if any, met the requirement. This method of solution, however, is too tedious and too difficult because of the large number of possible combinations, and in other problems where many more bridges are involved it could not be used at all."

Euler's alternative method is much simpler. He showed that a tour of the kind sought must exist if the graph meets two conditions. First, it must be possible to go from any point in the graph to any other point by following the lines of the graph: in other words, the graph may not be disconnected. Second, every point of the graph, with two possible exceptions, must be at the junction of an even number of lines.

It is not hard to understand why a graph cannot have an Eulerian path unless it meets these conditions. All regions of the graph must be connected to one another if there is to be any path that traverses all the lines. Each point must have an even number of lines because half of them are required to reach the point and the other half to leave it. Two points with an odd number of lines can be allowed if they are chosen as the starting and finishing points of the path. Demonstrating that any graph that meets these conditions actually has an Eulerian path requires a somewhat more complicated argument, which we shall not present here, but Euler was able to give a rigorous proof.

It is an easy matter to express Euler's solution to this problem in an algorithm that could be executed by a computer. The first requirement, connectivity, can be established by marking some point of the graph, then similarly marking all points connected to it by lines, then all the points connected to the newly marked points, and so on. The graph is connected if at the end all points have been marked. The second requirement is just as easily tested: the machine is instructed to examine each point of the graph and count the number of lines that terminate at that point. If no more than two of the points have an odd number of lines, the graph has an Eulerian path. The park at Koenigsberg met the first condition but not the second, and so there was no Eulerian tour of the seven bridges.

Euler's method is unquestionably the more economical approach to the problem of Koenigsberg bridges: it requires that each point and line of the graph be listed just once, whereas the exhaustive search is not completed until every path that crosses all the bridges has been listed. The number of such paths is much larger than the number of points and lines in the graph. In that sense Euler's method is the better algorithm, but how much better? How can the difference be measured and how can one fell if the difference is significant?

For a graph with only four points and seven lines both techniques are fast enough to be considered practical. Suppose, however, that more islands and bridges were added to the park, or in other words that more points and lines were added to graph. If the problem is being solved by Euler's method, each new point merely adds one item to the list of points that must be checked. If the paths are to be examined by exhaustive search, on the other hand, then with each new point and line the size of the list is multiplied by some factor. A moderate increase in the size of the graph results in an explosive increase in the number of paths. Ultimately the list of paths 'must become prohibitively long.

In this comparison of the two solutions to Euler's problem there is the basis for a completely general method of evaluating the speed or practicality or efficiency of any algorithm. We imagine that the algorithm is supplied with larger and larger inputs, and we note the rate at which the execution time of the algorithm increases. In this way it is possible to make unequivocal judgments of algorithms. Exhaustive search not only is a slower method; in general it is too slow to be of any value. Euler's method remains practical for problems of essentially unlimited size.

As the size of the graphs being examined increases, the lists produced by the method of exhaustive search grow exponentially. Each time some fixed number of points and lines are added to the graph the size of the list doubles. Growth of this kind can be described by a mathematical function such as 2^n, where n is some measure of the size of the graph. Many other functions have similar or even higher rates of growth. Among them are n^n and n! ( which is read as "n factorial" and signifies n multiplied by all the integers between 1 and n). For the purposes of this discussion all these functions can be regarded as having the same property of exponential growth.

Mathematical functions of another kind are known as polynomials. The simplest members of this class are linear functions, such as 3n, which designate a simple relation of proportionality. The time needed to solve the problem of Koenigsberg bridges by Euler's method increases as a linear function of the size of the graph. Other polynomials are n^2, n^3 and so on, and the sums of such functions. What distinguishes polynomials from exponential functions is that n never appears in an exponent.

For sufficiently large values of n any exponential function will overtake and exceed any polynomial function. It was the certainty of this result that dismayed 'Ihomas Malthus when he compared the exponential rate of population growth with the polynomial rate of increase in the food supply. For small values of n a given polynomial function may well exceed a given exponential one, but there is always a value of n beyond which the exponential function is the greater. The exact form of the polynomial makes little difference, except in changing the point at which the polynomial function is overtaken.

It is now generally agreed by computer scientists that algorithms whose execution time increases exponentially as a function of the size of the input are not of practical value. We shall call algorithms of this kind "exponential time" algorithms, or simply inefficient algorithms. The only algorithms that are considered fast or efficient enough for general application are "polynomial time" algorithms.

Of course, even among efficient algorithms some are faster than others, but for the purposes of this discussion it is important only to distinguish polynomial-time algorithms as a class from exponential-time algorithms. Moreover, this system of classification has the advantage that it makes the speed of an algorithm a property of the algorithm itself and independent of the machine on which it is executed. For sufficiently large problems a polynomial-time algorithm executed on even the slowest machine will find an answer sooner than an exponential-time algorithm on the fastest computer.

The mathematical properties of algorithms were studied in the 1930's by the British mathematician A. M. Turing, the inventor of the imaginary computer, now called a Turing machine. The Turing machine was conceived to be an automaton equipped with an infinite supply of paper tape marked off in square regions. The machine was capable of just four actions: it could move the tape one square, it could place a mark in a square, it could erase a mark already present and at the end of a calculation it could halt. These operations were to be performed according to a sequence of instructions built into the internal mechanism. Of course, Turing never built such a machine; it was merely a conceptual device for automatically solving problems in mathematics and logic. Indeed, Turing was interested not in actually solving problems with the machine but rather in investigating what kinds of problems it could solve and what kinds it could not.

Turing discovered that even a machine as simple as this one could solve any problem for which an algorithm could be devised. The computation might be laborious and indirect, but given enough time and paper tape the machine would eventually find the solution and halt. Reduced to its essentials the Turing machine is a language for stating algorithms, as powerful in principle as the more sophisticated languages now employed for communicating with computers.

In addition to conceiving, these machines Turing demonstrated, their limitations. In 1936 he showed that there are problems that cannot be solved by Turing machines, and it follows that these problems cannot be solved by any automatic computer. They are problems for which algorithms cannot be written, even in principle. The example first studied by Turing is the problem of predicting whether a particular Turing machine, once it is set in motion, will ever finish its calculation and halt. Through an analysis of this problem he was able to show that there can be no general procedure for telling whether mathematical propositions are true or false. Since then a variety of other problems with the same properties have been proposed.

One result of Turing's work was to divide all imaginable problems in mathematics into two classes. Those problems for which algorithms can never be written are in a formal sense permanently unsolvable. Some instances of these problems may be solved by rare perception or by luck, but a general method for their solution will never be found.

All other problems in mathematics and logic can be solved by algorithms. As we have seen, however, some algorithms are more useful than others. The class of solvable problems can therefore be divided into two subgroups: those for which there are efficient, polynomial-time algorithms and those for which there are only exponential-time algorithms. Euler's problem is a member of the class with polynomial-time solutions, since Euler's method is itself a polynomial-time algorithm. Problems that can be proved to have only exponential-time algorithms are also known, although they are rather obscure.

Although these two groups of problems are quite distinct, it is not always a straightforward task to assign a problem to one group or the other. Indeed, a very interesting class of problems seems to fall somewhere between them. For these problems no efficient algorithms are known and the best available solutions require exponentially increasing time, yet no one has been able to prove that the problems do not have polynomial-time solutions.

One such problem was considered in the 19th century by the Irish mathematician William Rowan Hamilton. Superficially Hamilton's problem is much like Euler's .The problem is to decide whether a given graph has a path that takes in each point exactly once (whereas Euler looked for a path that traversed each line once). Actually the tasks are quite different, and Euler's method cannot be applied to Hamilton's problem. The graph derived from the plan of the park at Koenigsberg has a Hamiltonian path, although, as we have seen, it has no Eulerian path. On the other hand, removing two lines results in a graph that has an Eulerian path but not a Hamiltonian one. Many other graphs have neither kind of path.

Hamilton's problem can be solved by exhaustive search: indeed, the procedure is not substantially different from that employed in listing all the possible paths that might have the Eulerian property. For Hamilton's problem, however, no efficient algorithm comparable to Euler's method has been found. The problem has been pondered by many of the best mathematicians of the past century, but the most efficient methods available today are fundamentally no better than exhaustive tabulation. On the other hand, all attempts to prove that there is no better method have also failed, and it must be considered a possibility that an efficient algorithm will be discovered tomorrow.

Problems that are known to have polynomial-time solutions, such as Euler's problem, are said to be members of the class P (for polynomial). Hamilton's problem is a member of another class, designated by the letters NP, signifying "nondeterministic polynomial." The class NP encompasses all the problems in P, or in other words P is a subset of NP. In addition NP includes problems whose status is less certain. They are all solvable problems in principle: they have algorithms, but for now only exponential-time algorithms are known. They may also have polynomial-time algorithms (in which case NP and P are identical) or they may prove to be permanently intractable, with only inefficient solutions.

The problems considered here, and all problems classified in this way, can be described as an infinite set of similar questions each of which can be Another way of defining NP is as the class of yes-or-no problems that can be solved by guessing certificates. If one is given an instance of a problem in NP for which the answer happens to be yes, then with luck one may discover the required certificate fairly quickly by making a sequence of guesses; if the answer is no, guessing cannot possibly yield an answer any faster than an exhaustive search could. For example, in solving Hamilton's problem one might find a correct path (if there is one) on the first try by tracing small portions of the path and guessing at each stage how to proceed. Such a procedure, it should be emphasized, is not an algorithm. It could be made into an algorithm only by crossing off each trial path as it is tested and checking all possible paths, but that is equivalent to the method of exhaustive search.

A mathematical procedure defined in terms of luckly guesses may seem bizarre, but it is a quite legitimate approach to defining the problems in the class NP. In principle the procedure could even be mechanized by building a device called a nondeterministic Turing machine. This device can do all that an ordinary Turing machine can do; in addition, at some points in its operation it may have more than one choice of what to do next. Such a machine would be considered to answer yes to a question if there were some sequence of choices that could lead it to a yes conclusion. NP, the class of nondeterministic polynomial-time problems, consists of precisely those problems whose yes instances can be identified by, machines making comparatively short guessing computations.

The inclusion of guessing in the definition of these problems suggests strongly to many mathematicians that P and NP are not the same set and hence that efficient algorithms can never be found for the intractable problems in the class NP. If every problem in NP were actually in P, then all the guesswork and luck could be replaced by some systematic procedure without great sacrifice in time. It is hard to believe the ability to guess and be lucky could win so little.

The class NP includes a variety of commonly encountered problems that seem to defy efficient solution. We have already mentioned Hamilton's problem and the problem of composite numbers. Another example is known as the matching problem. It can be considered in terms of the task faced by the colleges every September, when a new class of freshmen must be assigned to shared dormitory rooms.

For the sake of simplicity let us assume that all the information gathered about the students' smoking habits, bed time hours, taste in music and so forth results in a single yes-or-no decision as to the compatibility of each possible pair of students. The entire class can then be represented as a graph in which the points correspond to students and a line is drawn answered yes or no. For problems that are formally unsolvable, such as the problem of predicting whether a Turing machine will halt, these questions simply cannot be answered by any algorithmic procedure. For problems of the class P the questions can invariably be answered, whether the answer turns out to be yes or no, by an efficient procedure. In order for a problem to qualify for the class NP there need not be an efficient means of answering the yes-or-no questions. What is required is that whenever the answer is yes there be a short and convincing argument proving it.

Hamilton's problem, for example, meets this condition. It is not possible to tell by any efficient means known today whether a graph has a Hamiltonian path, but if it does, then the path itself can be exhibited. Hence for every Hamiltonian graph it is possible to issue a "certificate" that proves its membership in this special class of graphs. Such a certificate would name the lines in the graph in the order the path traverses them. Finding the path might require weeks of tabulation, but once it has been found it can easily be exhibited. Another problem that belongs to the class NP is the question of whether a whole number is composite, that is, whether it can be written as the product of two other numbers. Again there is no known efficient procedure for answering the question, but if the number is indeed composite there is a succinct proof of that fact, namely a correctly worked-out multiplication with the number on the bottom line.

Care must be taken when asking the yes-or-no question of a problem in the class NP, since the complementary no-or-yes problem might not be in the same class. For example, the complement of Hamilton's problem, in which one is asked to show that a graph does not have a path passing once through each point, may well not be in the class NP. For now the only way to demonstrate the absence of such a path is to list all possible paths, and such a proof is too lengthy to qualify as a certificate of membership in NP. On the other hand, the complement of the composite-number problem, which asks if a number is prime, turns out to be in the class NP. The reason, which is far from obvious, is that relatively short proofs demonstrating that a number has no factors other than 1 and itself were discovered in 1975 by Vaughan Pratt of the Massachusetts Institute of Technology. Still, it is not known whether the composite-number problem and its complement are in the class P.

It is easy to show that every problem in the class P is also in the class NP. If a problem is in P, then by definition there is an efficient algorithm for it. To produce a short and convincing proof that the answer to some instance of the problem is yes, all we need to do is follow the algorithm: a record of its operation constitutes the required certificate.

Another way of defining NP is as the class of yes-or-no problems that can be solved by guessing certificates. If one is given an instance of a problem in NP for which the answer happens to be yes, then with luck one may discover the required certificate fairly quickly by making a sequence of guesses; if the answer is no, guessing cannot possibly yield an answer any faster than an exhaustive search could. For example, in solving Hamilton's problem one might find a correct path (if there is one) on the first try by tracing small portions of the path and guessing at each stage how to proceed. Such a procedure, it should be emphasized, is not an algorithm. It could be made into an algorithm only by crossing off each trial path as it is tested and checking all possible paths, but that is equivalent to the method of exhaustive search.

A mathematical procedure defined in terms of luckly guesses may seem bizarre, but it is a quite legitimate approach to defining the problems in the class NP. In principle the procedure could even be mechanized by building a device called a nondeterministic Turing machine. This device can do all that an ordinary Turing machine can do; in addition, at some points in its operation it may have more than one choice of what to do next. Such a machine would be considered to answer yes to a question if there were some sequence of choices that could lead it to a yes conclusion. NP, the class of nondeterministic polynomial-time problems, consists of precisely those problems whose yes instances can, be identified by machines making comparatively short guessing computations.

The inclusion of guessing in the definition of these problems suggests strongly to many mathematicians that P and NP are not the same set and hence that efficient algorithms can never be found for the intractable problems in the class NP. If every problem in NP were actually in P, then all the guesswork and luck could be replaced by some systematic procedure without great sacrifice in time. It is hard to believe the ability to guess and be lucky could win so little.

The class NP includes a variety of commonly encountered problems that seem to defy efficient solution. We have already mentioned Hamilton's problem and the problem of composite numbers. Another example is known as the matching problem. It can be considered in terms of the task faced by the colleges every September, when a new class of freshmen must be assigned to shared dormitory rooms.

For the sake of simplicity let us assume that all the information gathered about the students' smoking habits, bed time hours, taste in music and so forth results in a single yes-or-no decision as to the compatibility of each possible pair of students. The entire class can then be represented as a graph in which the points correspond to students and a line is drawn connecting every two students who can be placed in the same room. If each room holds just two students, the assignment can be made efficiently by a clever polynomial-time algorithm discovered by Jack Edmonds of the University of Waterloo. If each room is to be shared by three students, however, there is no known efficient algorithm. The problem is in the class NP, since all yes instances have succinct certificates: an acceptable room assignment, once it is discovered, can easily be exhibited. Of course, a solution could be found by exhaustive search, albeit inefficiently. With luck a suitable assignment, if there is one, can be guessed quickly.

Map coloring is a problem in the class NP that concerns mathematicians more than it does cartographers. The question is whether the countries on a given map can be colored with a given number of colors so that no two countries that share a border have the same color. It is easy to find out if a map can be colored with two colors, it can be if there are no places on the map where an odd number of countries meet at one point. It is even easier to tell if a map can be colored with four colors; indeed, there is no need even to look at the map, since Kenneth Appel and Wolfgang Haken of the University of Illinois proved in 1975 that four colours suffice for any map. Surprisingly, however, no efficient algorithm is known for determining whether three colors are enough for a given map. The problem is in the class NP, since a correctly colored map can-serve to certify a yes answer.

Map coloring can be regarded as a special case of another problem called graph coloring. Any map can be converted into a graph by reducing each country to a point and drawing a line between two points if the corresponding countries share a border. Coloring the graph is then equivalent to coloring the map, subject to the rule that two points connected by a line cannot have the same color. Graph coloring, however, is a more general problem, with applications outside graph theory. For example, a graph can represent the scheduling of work in a factory. Each point of the graph stands for some job to be done, and two points are connected by a line, if the jobs cannot be done concurrently, perhaps because they require the same piece of machinery. A coloring of the graph with three colors would then supply a schedule dividing the work of the factory into three shifts. Like map coloring, the graph-coloring problem is in the class NP.

It often happens that if one problem can be solved efficiently, so can many others. For example, if an efficient algorithm could be found for the problem of graph coloring, it could be applied with only minor modifications to the problems of map coloring and factory scheduling. Map coloring and factory scheduling are therefore said to be efficiently reducible to graph coloring. In the past several years it has become apparent that some of the problems in the class NP have a remarkable property: all the problems in NP are efficiently reducible to them. These elite problems within the class NP are called NP-complete. If any one of them has an efficient algorithm, then every problem in NP can be solved efficiently.

The first proof that a problem is NP-complete was presented in 1971 by Stephen A. Cook of the University of Toronto. His reasoning follows a path essentially parallel to the path of Turing's earlier work on mathematical machines and their relation to problems of formal logic. Cook stated his proof in terms of the prepositional calculus, the formal language in which separate logical statements, which individually may be either true or false, are joined together by the lexical elements "and," "or" and "not." In general a sentence in the propositional calculus can be shown to be either true or false depending on which of its component statements are assumed to be true or false. Certain sentences, however, cannot be true under any interpretation because they are self-contradictory. Sentences that cannot be made true are said to be unsatisfactory.

Cook employed the propositional calculus to describe the operation of the nondeterministic Turing machines, the mechanized guessing devices essential to the definition of the class NP. He showed that the calculations of any such machine can be described succinctly by sentences of the propositional calculus. When the machine is given a yes insfance of a problem in NP, its operation is described by a satisfiable sentence, whereas the operation of a machine given a no instance is described by a sentence that cannot be satisfied.

It follows from Cook's proof that if one could efficiently determine whether a sentence in the propositional calculus can be satisfied, one could also determine efficiently in advance whether the problem presented to a nondeterministic Turing machine will be answered yes or no. Since the problems in the class NP are by definition all those that can be solved by nondeterministic Turing machines, one would then have an efficient method for solving all those problems. The catch, of course, is that there is no known efficient method of determining whether a sentence in the propositional calculus can be satisfied.

Cook's argument states in essence that the propositional calculus is a universal language for describing problems in the class NP. Every instance of such a problem corresponds to a sentence in that language, and if the sentence is satisfiable, the instance has a yes answer. Many other problems have since been shown to be NP-complete because the satisfiability problem can efficiently be reduced to them. Hamilton's problem, the problem of matching groups of three roommates and the problem of coloring graphs with three colors are all NP-complete. The first to point out the broad applicability of this theory was Richard M. Karp of the University of California at Berkeley. Similar investigations were independently conducted by the Russian mathematician P. A. Levin. Since NP-complete problems capture the difficulty of all other problems in NP, it is widely thought today that all NP-complete problems are computationally intractable. A proof that a problem is NP-complete is usually considered a strong argument for abandoning further efforts to devise an efficient algorithm for its solution.

Even the assumption that all NP-complete problems are intractable would not settle all questions about the class NP. In addition to the mystery of the NP-complete problems there is an even more obscure area: problems in NP for which no efficient algorithms are known but which have not been proved to be NP-complete either. The problem of composite numbers is one of these.

Not all problems that can be solved by a computer are of the yes-or-no. type. Another common type is the optimization problem. For example, suppose one is given the positions of some cities on a map and asked to find the shortest possible railroad network connecting them. In one version of this problem one is allowed to lay down a straight section of track between any two cities, but one is not allowed to install isolated junction points; tracks can be joined only at cities. One property of the solution to this problem is immediately apparent: the optimum network can never include a closed circuit, because if it did, the network could be made shorter simply by omitting one link in the circuit. Thus the best net-work always branches like a tree, and the problem itself is called the spanning-tree problem.

The spanning-tree problem can be solved correctly and quite efficiently by a method called the greedy algorithm, devised by Joseph B. Kruskal of Bell Laboratories. The procedure is simply to connect the closest pair of cities, then the next-closest and so on without adding any superfluous lines (lines joining cities that are already linked indirectly). It is far from obvious that this method always yields the shortest network, but it does, and it has the pleasant property of requiring no foresight and no reconsideration of earlier decisions.

The greedy algorithm can be relied on to find the shortest network between cities under the rules specified, but in general that network will not be the shortest possible one. Further savings can be achieved by establishing junction points between cities. The properties of networks with such junctions were studied by the Swiss mathematician Jakob Steiner. It can be shown that any shortest network must be arranged so that each junction point is made up of three lines that meet at angles of 120 degrees. This rule provides some guidance in evaluating networks, but there are many possible networks with Steiner junction points. No algorithm has been discovered that finds the best network quickly.

The problem of the traveling salesman's tour is closely related. Again one is given a set of cities, but now one is asked to find the shortest round-trip tour. As a first guess the greedy algorithm suggests that perhaps the salesman should always go to the nearest city he has not yet visited, but this procedure does not work. Indeed, the problem is notorious for having resisted all attempts to find an efficient solution.

Optimization problems are not fundamentally different from those that ask yes-or-no questions; in fact, every optimization problem can be rewritten in a yes-or-no form. In the traveling salesman problem, for example, we might be given a length along with a set of cities and asked to state whether a tour can be constructed that does not exceed the specified length. This yes-or-no problem cannot be harder than the associated optimization problem, because if the optimum tour could be found by some efficient method, it would be a trivial task to determine whether it exceeds a given number. Hence if the yes-or-no version is computationally intractable, one cannot hope to solve the optimization problem itself efficiently. For this reason certain optimization problems, such as that of the traveling salesman's tour and that of placing Steiner junction points, are said to be

NP-complete.

Optimization problems are encountered often in engineering, economics, operations research and other fields. The discovery that at least some of these problems are NP-complete is therefore of considerable practical interest. Since the NP-complete problems probably have no efficient algorithms, there would seem to be little point in expending further effort in seeking optimum solutions. An alternative that has recently been adopted is to seek approximate solutions that are good even if they are not precisely optimal.

One technique that has been applied to the traveling salesman problem offers a solution that may not be optimum but is guaranteed to be no worse than twice the optimum path. The procedure starts with the shortest spanning tree, which can be generated efficiently by the greedy algorithm. This network can be converted into a tour of the cities by traversing each line twice and returning to the origin. It is known that the optimum spanning tree must be shorter than any possible tour of the cities, since a tour can be converted into a spanning tree (albeit one without any branches) by simply omitting one segment. Thus twice the length of the optimum spanning tree cannot be longer than twice the optimum tour. The method is a polynomial-time algorithm. Recently Nicos Christofides of the Imperial College of Science and Technology in London has found a way to improve the algorithm so that it yields a tour guaranteed to be no more than half again as long as the optimum.

A more profound compromise gives up not only the requirement that a solution be optimal but also the insistence that a less than optimum solution be guaranteed to fall within a specified range. Instead the assurance is given that the solution will not often deviate far from the optimum. An underlying assumption of such techniques is that the maps encountered in practice are not concocted to confound basically plausible techniques; such maps are encountered frequently only when they are constructed by computer scientists to reveal the flaws in methods proposed by their colleagues. Indeed, if the salesman's tour algorithms discussed above are applied to "natural" maps, they deliver far more than they promise. The resulting tours are not 100 percent or 50 percent longer than the optimum but closer to 5 percent.

A reasonable assumption about the properties of many maps is that cities are randomly placed. A theorem describing the statistical properties of optimum tours through such randomly distributed points was proved in 1958 by Jillian Beardwood, J. H. Halton and John M. Hammersley of the University of Oxford. Relying on that theorem, Karp has shown that a simple method of constructing tours almost always yields near-optimum results, when it is applied to maps with many cities.

 Karp begins by dividing the map into many small regions. Within each of these regions the cities are sufficiently few to find the optimum tour by exhaustive search, even though that method involves an exponential-time algorithm. The tours of the small areas are then linked by a variant of the greedy algorithm. Perhaps significantly, the method is not very different from the method usually adopted by people solving the problem manually.

Efficient but approximate solutions can be found for many NP-complete optimization problems. From the standpoint of mathematics, however, the important question is whether NP is identical with P. The repeated failure of attempts to find an efficient algorithm for the NP-complete problems has created considerable confidence that NP and P are not the same. There is now suspicion that they are not identical, but the proof of their distinctness may be beyond present mathematical capabilities. The question may join that select group of mathematical enigmas that remain unresolved for decades, and the solution may have to await the development of new methods in mathematics.