|
|
|
Computational Perplexity |
|
|
|
|
On October 14, 1947, Chuck Yeager, flying in an experimental jet aircraft, was the first human being to fly faster than the speed of sound. I know this random factoid because last night Jo and I watched "The Right Stuff" a movie about test pilots and the NASA Mercury 7 astronauts based on a book by Tom Wolfe. Yeager broke what at the time was called the sound barrier which some engineers believed would prevent aircraft from ever flying faster than sound. The "sound barrier" was not a fundamental limitation and eventually engineers found a way to overcome the increase in drag and loss of control that result from the (shock) waves of compressed air produced as an aircraft approaches the speed of sound. There are fundamental limitations, however, and the history of science and engineering is as much about understanding real limitations and circumventing them as it is about debunking myths and crashing through imaginary barriers. The history of theoretical computer science and the theory of computational complexity in particular is about understanding and overcoming fundamental computational limitations.
There's a story in the introductory chapter of a well-known text about the theory of NP-Completeness [Garey and Johnson, 1979] that tells of a programmer who goes to his boss and tells him that he can't make his program run any faster because the problem he's trying to solve is in the class of NP-complete problems. The class of NP-complete problems is a class of computational problems such that, if you could solve any one of them easily, then you could solve all the others easily as well. It is conjectured that the problems in this class are intractable in the sense that an algorithm that solves one of these problems is going to require an amount of time that scales exponentially in the size of the problem. (see the journal entry on analyzing various algorithms for computing the nth element of the Fibonacci sequence for a discussion of what it means for an algorithm to scale exponentially or linearly in n). Unfortunately, the programmer couldn't say to his boss that it was impossible to write an efficient algorithm (one that, say, scales linearly or polynomially in the problem size) but only that no one has yet done it and there are a lot of computer scientists who believe it can't be done. The problem of proving whether or not the class of NP-complete problems is composed of intractable problems is one of the most interesting open problems in the theory of computation. Is NP-completeness a fundamental limitation or simply a limitation of current technology like the sound barrier was in 1947? Before I try to answer this question, I'd like to look at a few other questions concerning the fundamental limitations of computers that have been resolved over the years.
In 1930, Kurt Gödel was the first to show that any system sufficiently expressive to formally capture the machinery of arithmetic, the rules and definitions that describe numbers and how they must behave, must be incomplete in the sense that there are assertions in that formal system that can neither be proved or disproved. The realization that the tools of mathematics were not up to the task of discovering the whole of the truth about mathematics was a profound shock to many mathematicians of the time, but Gödel's proof has broader implications that were yet to be understood.
Gödel's proof left open the possibility that there was a mechanical procedure, an algorithm, that would allow us to determine for a given assertion if that assertion is decidable, whether it is provable or not. Alan Turing was able to show that no such mechanical procedure exists (the problem of determining whether an assertion is probavable or not is therefore said to be indecidable) and that moreover, since we can represent in a suitably expressive language assertions of the form, "this computer program will halt", there is no mechanical procedure, no computer program, that can determine for any other computer program whether or not that program will halt. This is the so-called halting problem. In a formal sense then, Turing showed that there are some problems that cannot be solved by any algorithm running on any computer.
Turing also conceived of and then was able to demonstrate the existence of a general-purpose or universal computer that can solve any problem solvable by a special-purpose computer. Indeed, the idea of a universal computer is not all that difficult to comprehend for us given our familiarity with modern day computers. The abstract computer that underlies the von Neuman architecture which we discussed on July 26th is a universal computer but for one problem, it lacks a memory of infinite capacity. Turing's universal computer required a tape on which to read and write bits and, in order to be able to carry out any computation, that tape had to be infinite in length. Practically speaking, modern day computers have sufficient memory, RAM and disk storage, to perform most computations that we might care to think about; they are not, however, universal computers as defined by Turing.
The word complexity1 is the source of much perplexity2 on the part of computer science professionals and dilettantes alike. The standard dictionary definitions of the word provide little hint as to the technical meaning (or meanings) of the word. What makes one computer problem more complex than another? One measure of complexity of interest to computer scientists concerns how long it takes a computer to solve a particular problem. Another related measure concerns how much memory or space is required to solve a given problem.
Computer scientists aren't interested in how fast a program runs on a 1.5GHz Pentium III running Microsoft Windows versus a 1.2 GHz PowerPC G4 running Apple OS X. Or how much time on the clock or megabytes of RAM it takes an algorithm to complete a task. Like any good mathematician, a theoretical computer scientist abstracts from the irrelevant details to get at the heart of the matter. Time is measured in terms of the number of basic operations required to complete a computation. In comparing various algorithms for computing the nth element of the Fibonacci sequence, we used the number of additions as a function of n as our measure of complexity. Space is measured by how many bits using a standard encoding are required to represent the intermediate and final products of a computation. The algorithms for computing the nth element of the Fibonacci sequence used only integers for their intermediate and final results but other algorithms require the use of more complicated data structures which require significant space overhead.
The problem of computing the nth element of the Fibonacci sequence is an easy one as computational problems go. There exists an algorithm which I presented that runs in time linear in n. Other problems require time that scales polynomially (e.g., n2) in the size of the input which we will designate as n in the following. Polynomial scaling, often called polynomial time, is obviously worse than linear scaling, linear time, but for low-order polynomials (polynomials whose most significant exponent, e.g., 3 in the polynomial, 4 n3 + 2 n2 + 1, is relatively small), polynomial time is seldom a practical concern. Are there problems for which the fastest algorithms scale exponentially in n? The answer is yes. But a more interesting question is the following. Are there problems that we care about for which the fastest algorithms scale exponentially in n. And the answer to this question is at the heart of the theory of NP completeness.
Let P be the class of problems that can be computed in polynomial time. NP is the class of problems that can be computed in nondeterministic polynomial time. These problems are characterized by the property that you can check whether or not a proposed answer to one of these problems is correct in polynomial time. Therefore you could solve the problem by nondeterministically choosing a possible solution and then checking it. If you were always lucky and chose a correct answer then you would be able to solve the problem in polynomial time. The class of NP-complete problems is a particular class of problems that are in the class NP but that are not known to have polynomial time solutions, indeed every known algorithm for these problems runs in time that scales exponentially in n, i.e., exponential time. Besides the fact that the best-known algorithms for these problems take exponential time, the class of NP-complete problems is interesting for three reasons: First, if you could solve one problem in this class in polynomial time, then you can solve all of them in polynomial time. Second, this is about as easy a class as one could imagine and still not be known to be in P. And, third, the class of NP-complete problems contains a bunch of problems that we really care about.
One of the most famous NP-complete problems concerns the problem faced by a traveling salesman in trying to minimize his travels in calling on his customers. The problem can be described as a graph with n nodes where each node represents the location of a customer and a link between two nodes indicates that there exists a route between the corresponding two locations and is labeled with the distance separating the locations. The problem is to find a tour (a path that begins and ends with the same node and that visits each node in the graph exactly once) whose length (the sum of labels on the links that comprise the tour) is minimal3 (see the July 7th entry for a discussion of graph-theoretic terms). This problem is important in a wide range of practical problems from scheduling commercial aircraft to routing garbage trucks in large metropolitan areas. Other NP-complete problems are important in genetic and pharmaceutical research and a host of otherwise unrelated problems from packing furniture to making computers run faster.
The mathematics involved in defining and characterizing the class of NP-complete problems is an extraordinary achievement attributed in no small measure to the work of Stephen A. Cook and Richard M. Karp among other early pioneers in theoretical computer science. Since the basic formulation, computer scientists have erected a hierarchy of classes of problems of increasing complexity and studied the complexity not only of problems for which we require exact answers but also problems for which we'll accept approximations. There remain many open questions but one in particular looms above all the others. The question can be stated quite succinctly. Is P = NP? If someone can find a polynomial-time solution to one problem in the class of NP-complete problems then all problems in the class will have been shown to have polynomial-time solutions.
Many computer scientists believe that P ≠ NP and so the classes are distinct and that eventually someone will prove that this is so. By the way, it's not particularly unusual for a mathematical problem to remain unanswered for years, decades or even centuries after first being posed. The celebrated "Last Theorem" of Pierre de Fermat (1601-1665) remained unproven for over three centuries until Andrew Wiles, aided by the accumulated wisdom of many mathematicians, managed to produce a formal proof which stood up to careful scrutiny. A proof that P ≠ NP will make it easier for the programmer that we talked about earlier to convince his boss that it's fruitless for him to keep working on a polynomial-time algorithm for an NP-complete problem. However, if it is determined that P = NP, the repercussions could be very interesting. Not only will NP collapse into P, but there will be additional collapses and compression within the complexity hierarchy. And if P = NP then are we missing something fundamental in our understanding of algorithms and computing machinery? Why haven't the best hackers in the world been able to find polynomial-time solutions to any of the problems in the eminently-practical and exhaustively-studied class of NP-complete problems? Well, perhaps "exhaustively studied" is a bit of an exaggeration; we've only been at this for a little over 50 years. The field is young. Perhaps you'll be the one to prove that P ≠ P or to turn the field topsy turvy by demonstrating a polynomial-time algorithm for the traveling salesman problem.
Douglas Hofstadter's "Gödel, Escher, Bach" is a very readable introduction to Gödel's work and its implications [Hofstadter, 1979]. "Alan Turing: The Enigma" by Andrew Hodges is a wonderful introduction to the life and work of Alan Turing [Hodges, 1983]. Martin Davis [2000] wrote an interesting and entertaining book about universal computers and the logicians and mathematicians from Leibniz to Turing who provided the theoretical foundations for modern computer science. Martin Gardner's essay on the traveling salesman problem in "Gardner's Whys and Wherefores" [Gardner, 1989] provides a nice introduction to the ins and outs of the traveling salesman problem. David Harel's book [Harel, 2000] on the limitations of computers is an excellent introduction to the theory of NP-completeness. I also liked Harel's earlier book [Harel, 1987]. For an in-depth technical discussion of the broader field of computational complexity suitable for graduate-level study, I recommend [Papadimitriou, 1994].
The day after tomorrow, September 4, 2002, is our 32nd anniversary, much more significant for a computer scientist than the 25th or even the 50th. We just might possibly make it to the next significant landmark, the 64th, but the laws of exponential growth are pretty daunting.
I'm adding this postscript on September 5, 2002 after receiving feedback from several colleagues. My theoretically-minded colleagues call for precision in presenting theoretical results and my more practically-minded colleagues urge truth in advertising. In response, I summarized the high points of what I wanted to convey, underscored an important point about the open nature of the theoretical problems, and made a couple of points about the practical significance of NP-completeness results for software engineers. I've excerpted my responses below.
The most important point is that there are problems we actually care about, lots of them in fact, that are likely to remain beyond us for a considerable time to come. We can't compute solutions to these problems even though we know how, in the procedural sense, because the problems require too much time and space, in the computational sense. The computational requirements for these problems increase so rapidly that they will likely outpace anything we can build for longer than we care to wait. Here's an illustrative example:
Suppose that you're trying to design an efficient algorithm that finds patterns in human DNA as part of a diagnostic test for a new cancer treatment. And suppose that the best-known algorithm for solving the pattern-finding problem runs in exponential time. For patterns of size 10, it currently takes several hours to run this algorithm. For the diagnostic test to be useful in a clinical setting, you need to be able to solve the pattern-finding problem for patterns of size 100 in a matter of minutes. Even if you could rely on the speed of computers doubling - improving exponentially - every year on average for the foreseeable future, you'd still have to wait 90 years before your diagnostic test will run quickly enough to be useful to patients.
I want to make it clear that we don't know for sure that NP-complete problems require exponential time for their solution; only that a fair number of well-respected computer scientists believe that NP-complete problems will require exponential time to solve. The problem is still open; the class NP could collapse into P and therein lies the mystery and the challenge. A mystery whose resolution will likely have a much greater practical impact than the incompleteness results of Gödel or the indecidability results of Turing. This short piece attempts to empathize with the perspective of the theoretician and instill in the consciousness of proto theoreticians the thrill of the chase and the cosmic mystery of the abstract impinging on the concrete.
Beginning students and experienced practitioners alike often fail to make the distinction between problems and instances of problems and between problems and algorithms or programs for solving those problems. A particular instance of the traveling salesman problem involving, say, ten cities is not of much interest to a theoretical computer scientist. It may be hard to find an answer to this particular problem, but once you do, then you're done; the problem is solved. The traveling salesman problem is really set of instances with an infinite number of instances involving ten cities, an infinite number of instances involving eleven cities and so on. It's this infinite set of instances whose sizes are measured in terms of the nodes and links and labels of the graphs representing the cities and the distances separating them that constitutes the traveling salesman problem. And while a particular algorithm or program implementing an algorithm may scale linearly, polynomially or exponentially in the size of the problem instances the algorithm is given, complexity results are about problems, not particular algorithms. Such results, called asymptotic worst-case complexity results, seek to characterize the best we can expect of any algorithm under the worst possible circumstances, i.e., how the best algorithm scales as a function of the size of the problem instances it is given having been subjected to the hardest possible problem instances. Note that if there were only a finite number of instances it would be possible to solve each of them in finite time and, hence, the most efficient algorithm would solve them in advance of being asked and then simply profer the stored answer when asked for the solution to a particular instance.
I should also note that whether or not P = NP, the fact that a problem is NP-complete doesn't mean we stop working on it; the story about the programmer making excuses to his boss is misleading in this regard. You often hear programmers say that everything interesting or useful that's not trivial is NP-complete or worse. Their advice is to stop complaining about NP-completeness and get on with it. From their perspective, if P = NP, then they're no worse off than they were before, since they never had the luxury of telling their boss that there are no better algorithms. These programmers have to invent heuristics and uncover hidden structure in special classes of problems in order to solve or approximate the problems they are stuck with. If P ≠ NP, their heuristics may end up being the best we can hope for. Either way, they have to pound their heads against hard, seemingly intractable problems and come up solutions. In the case of our hypothetical diagnostic test for the cancer treatment, if the treatment appears to help patients, then programmers will do their best to find an approximate solution to the pattern-finding problem so that the diagnostic test will run in a reasonable amount of time and with an acceptable probability of error.
1. Here's what Merriam Webster's Collegiate Dictionary has to say about the colloquial uses of the word.
Main Entry: com.plex.i.ty Function: noun Date: 1685 1 : the quality or state of being complex 2 : something complexMain Entry: com.plex Function: adjective Etymology: Latin complexus, past participle of complecti to embrace, comprise (a multitude of objects), from com- + plectere to braid Date: circa 1652 1 a : composed of two or more parts : composite 1 b (1) of a word : having a bound form as one or more of its immediate constituents (2) of a sentence : consisting of a main clause and one or more subordinate clauses 2 : hard to separate, analyze, or solve 3 : of, concerned with, being, or containing complex numbers
2. I most like the word "perplexity" for its meaning of "entanglement".
Main Entry: per.plex.i.ty Function: noun Etymology: Middle English perplexite, from Middle French perplexite, from Late Latin perplexitat-, perplexitas, from Latin perplexus Date: 14th century 1 : the state of being perplexed : bewilderment 2 : something that perplexes 3 : entanglement
3. Technically, all of the problems in the class of NP-complete problems are decision problems which means they must have yes-or-no answers. In order to turn the traveling salesman problem, as it is called, into a decision problem, we would have to phrase it as follows: Does there exist a tour whose length is less than k for some fixed threshold k?