Chapter 12

Analyze This

Most physicists believe that the speed of light is a fundamental limit on how quickly we can move through space. This claim is based on the predictions of mathematical theories and the results of experiments that appear to support them. According to theory, it doesn’t matter whether you move through space with a pogo stick or an anti-matter drive, you’re still subject to the rules governing all matter in the universe and thus unable to exceed the speed of light.

What if there are limits on what you can compute? Pharmaceutical companies simulate interactions at the atomic level in searching for molecules to cure diseases. There could be viruses for which it will take years to find a vaccine — there is simply no way to speed up the necessary computations. Software developers who write the programs that keep airplanes flying and emergency rooms functioning would like to prove that their code won’t malfunction and put lives at risk. But maybe it’s impossible to provide such assurances.

In some cases, computational limitations can work to our advantage. Some programs exploit the difficulty of computing answers to particular problems; for example, the most popular encryption schemes for transferring information securely on the World Wide Web rely on the difficulty of computing the prime factors of large composite integers. Of course, if someone figures out how to factor large numbers efficiently, our privacy will be seriously threatened. It would be nice if we could guarantee the security of our encryption schemes.

Many computer scientists believe that there are fundamental limits to computation. Specifically, they believe that some problems are so hard it would take an impractically long time to compute their answers and that other problems simply can’t be solved. Theoretical computer scientists try to resolve fundamental questions about the limitations of computing as well as shed light on the performance of programs that we depend on every day.

Computer science as a discipline behaves at times like a physical science — computation is, after all, a fundamental determiner of change in the universe — and at times like a kind of engineering — modern software systems are among the most complicated artifacts ever created so it’s not surprising that computer science has its own theoretical foundations and a large body of engineering knowledge.

In this chapter we’re going to look at how computer scientists analyze problems. We’ll consider various mathematical models that provide general techniques for describing computations and quantifying their performance. And, finally, we’ll talk about theories concerning fundamental questions about what can and cannot be computed.

12.1  Analyzing algorithms

We started off Chapter 4 by distinguishing between specifications and implementations and in so doing we introduced two components of specifications, algorithms and data structures. An algorithmis a step-by-step recipe for how to carry out a given computation; the factorial procedure we looked at in Chapter 5 is such a recipe. A data structureis a strategy for organizing and manipulating data; lists and stacks together with their associated operations are examples of data structures. The relevant subfield of theoretical computer science is often called the “design and analysis of algorithms and data structures” or just “algorithms.”

A specification describes a computation independent of any programming language or computer hardware with which we might implement that computation. In theoretical computer science, algorithms and data structures are typically specified in terms of a pseudo-language that doesn’t correspond to any particular programming language used in practice. Doing this levels the playing field: anyone can understand such specifications and easily translate them into one or another programming language for implementation.

But while the algorithms and data structures that comprise a specification are language- and machine-independent, they must nonetheless connect to some model of computation in order to be comprehensible to us as computations. We’ve seen several models of computation, for example, the substitution model in Chapter 5 and the register-machine model in Chapter 9, that would be appropriate for this purpose. For a detailed analysis, we’d have to expand and be more precise about these models, but when we talk about an underlying model of computation for a given analysis you can safely think about one of these two.

Indeed, theoretical computer science abounds with interesting formal computational models. Every such model provides a mathematical framework in which one can talk about how information is represented and how computations proceed. These abstract models let theorists investigate what can be computed and how hard (how much time and memory they require) such computations are likely to be.

Not all computational models are equal, however, and so you can ask if one model of computation is more expressive than another in the sense that there are computations that you can specify in one but not in the other: One question often asked about a given model is whether or not you can tell if a computation specified in that model will halt. Sounds like a simple thing to require of a computational model, but many models turn out to be expressive enough that you can’t answer this question for all computations they can express.

Can you think of reasons why you’d want to adopt a less expressive, more restrictive model of computation? With some less expressive models you can get some nice properties, like the ability to check whether a computation will halt or a guarantee that every computation takes only a relatively short amount of time. Models with such properties might cramp your style somewhat, but they also might let you produce software with very desirable attributes.

We’re not going to worry about the more esoteric models, however. For our purposes, it suffices for you to think about computations in the register-machine model. For a generic programming language, we’ll use a variant of ALGOL(“algorithmic language”), which looks a bit like C. Here’s how to specify the square function in ALGOL:

integer procedure square(n)
    integer n;
    begin
        square := n * n 
    end;

Squint at the notation as usual, but note that the integer statements are “type declarations” (these would be int in C) and can safely be ignored, := indicates assignment¹ (x := 2 assigns to the variable x the value of 2) and, internal to the procedure definition, assigning the procedure name to a value (square := n * n) is the way to specify the return value for the procedure. You could then translate this ALGOL specification into Schemeas

(define (square n) (* n n))

or into Cas

int square(int n) { return n * n ; }

The touted advantage of using an agreed-upon standard like ALGOL is that everybody knows ALGOL (not true!) and that it doesn’t favor any particular language (well, O.K., ignoring dialects of ALGOL itself, in a way this is true, but it does favor languages with syntax similar to ALGOL). But this is one of the least interesting observations about the design and analysis of algorithms. You write algorithms in a general specification language to be clear about what they mean, to make it easy to implement them in a variety of languages, and to enable computer scientists to analyze their characteristics independent of the particular language in which they are written.

To illustrate how a computer scientist analyzes algorithms, we’ll look at a relatively simple mathematical algorithm: computing the nth term in the Fibonacci sequence. The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, ... so that the nth term for n greater than 1 is the sum of the n - 2 and n - 1 terms in the sequence. These so-called Fibonacci numbers may seem a bit academic but they have broad application, from a popular stock-trading strategy to the multiplication of rabbits.² Here’s how we might compute the nth term in the Fibonacci sequence in Scheme:

> (define (fibonacci n) 
     (if (= n 1) 0
         (if (= n 2) 1
             (+ (fibonacci (- n 2)) 
                (fibonacci (- n 1))))))
> (fibonacci 8)
13

And here is the same algorithm written in ALGOL, which doesn’t look too different from the Scheme implementation:

integer procedure fibonacci(n);
  integer n;
  if n = 1 
     then fibonacci := 0  
     else if n = 2 
             then fibonacci := 1 
             else fibonacci := fibonacci(n - 1) + 
                               fibonacci(n - 2);

Think about how many times the function fibonacci is called in order to compute the nth term in the Fibonacci sequence. It is called once in computing the first and second terms, three times in computing the third term, five times for the fourth term, and so on. Extending this sequence out a bit further, we get a new sequence: 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, ..., well, you can see the pattern; the nth term in this sequence is 1 plus the sum of the (n - 2) and (n - 1) terms. This sequence is upsetting to a theoretical computer scientist because it says that the work required to compute the nth term of the Fibonacci sequence approximately doubles each time n increases by 1; such a sequence is said to grow exponentially in n (think about 2ⁿ in which n is the exponent or power to which the base, 2 in this case, is raised).

In order to compute the 100th term of the Fibonacci sequence using this procedure, we would have to call the fibonacci function approximately 2¹⁰⁰ or 1,267,650,600,228,229,401,496,703,205,376 times.³ How long would this take? To keep our analysis simple, let’s focus solely on the arithmetic operations and let’s suppose that each addition (application of the + operator) takes on the order of a millionth of a second. I know it’s going to take a long time to perform the calculation, so let’s measure the time in years. How many seconds are there in a year?

> (* 60 60 24 365)
31536000

or around 32 million, ignoring leap years and such. And about how many seconds will our calculation take? (The exptor exponent function raises its first argument to the power specified by its second argument: (expt k n) returns kⁿ.)

> (* (expt 2 100) (/ 1 (expt 10 6)))
19807040628566084398385987584/15625

Oops, this version of Scheme is trying to be clever by returning the answer I requested as a rational number. It does this so it doesn’t have to give me an approximation of what I asked for. (How would you print out 1/3 as a “real” number? 0.33 or perhaps 0.3333333? Both of these answers are approximations to 1/3.) If I include a “real” number in the calculation, then Scheme tries to print the result as a real. Let’s try again:

> (* (expt 2 100) (/ 1.0 (expt 10 6)))
1.2676506002282293e+24

Well, I guess that’s progress! Now Scheme is offering me an approximation, but it displays it in scientific notation with a lot more precision (the digits to the right of the decimal point before e+24) than I can use. Let’s just say 1.27 * 10²⁴, which is a pretty big number. Since 31536000 is 3.1536000e+7 in scientific notation or approximately 3.15 * 10⁷, we can estimate that it would take 4*10¹⁶ years.

That’s an incomprehensibly long time and that’s just to compute fibonacci(100). Remember that things get exponentially worse as n gets larger, so fibonacci(101) takes twice as long as fibonacci(100):

> (/ (* (expt 2 101) (/ 1.0 (expt 10 6))) 
     (* 60 60 24 365))
8.039387368266294e+16

But when you think about it, this sort of performance just isn’t necessary. If you compute the sequence in order, remembering all the earlier terms (or at least the two most recent ones, the ultimate and the penultimate terms in the sequence seen so far), then computing the next term requires simply adding together the previous two terms. The only trick is to remember the previous two terms. Here’s an algorithm that exploits this idea:

integer procedure fibonacci(n);
  integer n;
  if n = 1 
     then fibonacci := 0
     else if n = 2
             then fibonacci := 1
             else begin 
                    integer penultimate; 
                    penultimate := 0;
                    integer ultimate; 
                    ultimate := 1;
                    integer temporary;
                    for i = 3 step 1 until n do 
                        begin
                            temporary := ultimate + 
                                         penultimate; 
                            penultimate := ultimate;
                            ultimate := temporary;
                        end ;
                    fibonacci := ultimate
                  end

In analyzing these two algorithms, a computer scientist would say that the first scales exponentiallyin n while the second scales linearlyin n. Assuming that each addition takes on the order of a millionth of a second and ignoring all other aspects of the computation, computing fibonacci(100) with the second algorithm would take considerably less than a second (10²/10⁶ = 1/10⁴ seconds). That’s quite a difference — and we got the improvement just by thinking about the solution in a different way.

My fooling around with Scheme to calculate how many times the fibonacci function is called wasn’t entirely gratuitous. Don’t believe anyone who tells you that computer arithmetic is simple; what goes on behind the scenes when you multiply and divide numbers in a calculator or general-purpose computer is fascinating and comprises an important subfield of computer science called numerical analysis. In analyzing some algorithms, it’s not enough simply to count the number of arithmetic operations; it can be necessary to look more carefully at how those operations are implemented. The numbers in the Fibonacci sequence quickly get very large thereby affecting the running time of the algorithm.

To represent a number n in binary you need around the logto the base 2 of n bits, which is typically written as . You may recall from high-school algebra that raising a number to a power (exponentiation) and taking logarithms are inverse operations, so that . The binary representation of a number requires one plus as many bits as the exponent of the largest power of 2 that the number can contain. So for example, 25 = 2⁴ + 2³ + 2⁰ is 11001 in binary, requiring bits. To perform operations on numbers you must at least read them and that means scanning every bit, so even something as seemingly simple as adding two numbers has to be thought about carefully. If you return to the discussion in Chapter 9 concerning computer arithmetic, you can figure out how many primitive operations are required to add and multiply integers.

Algorithms can scale in other ways than linearly or exponentially. For example, suppose you have a list of the birthdays of all your friends and you want to check to see if any of them have the same birthday. One algorithm for this check would be to consider each possible pair of friends and explicitly compare their birthdays. This algorithm is said to scale polynomiallyin n (the number of friends you have) because there are n² possible pairs, and hence the algorithm would have to perform n² comparisons (n² is said to be a polynomial of degree 2).

This isn’t a great algorithm for this problem, however. Here’s a better one. Sort the birthdays by date to produce a new list in chronological order and then scan this list to see if any consecutive items in the list are identical. Aside from the sorting part, this algorithm requires n comparisons to check for possible identical consecutive items. The sorting requires comparisons. The total number of comparisons is therefore , which is less than polynomial of degree 2 but more than linear. If n = 2¹⁰ = 1024, the n² algorithm does 1,048,576 comparisons while the algorithm needs only 11264 comparisons.

Here’s a quick and dirty implementation using a shell script and the sort and uniq commands (the -d option to uniq displays duplicates only — it does not output lines that are not repeated in the input):

% cat dates.txt
12.01
08.08
02.28
07.31
08.08
% cat dates.txt | sort | uniq -d
08.08

Could we manage with fewer than comparisons? How did I know that sorting a list of n items takes comparisons? You’ll discover the answer to these and many other interesting questions if you take a course on algorithms or consult a good book on the subject. The text by Cormen, Leiserson, Rivest and Stein is a little daunting in both size (it’s over 1000 pages) and mathematical detail, but it does provide a comprehensive introduction to algorithms and their analysis. David Harel’s book Algorithmics provides a somewhat less demanding and very entertaining introduction to the field.

In case it’s not already obvious, this branch of computer science uses a lot of mathematics. In analyzing algorithms, as in other highly mathematical areas of science and engineering, “getting it right” is important. Earlier I said that our first algorithm for finding a pair of friends with the same birthday scaled polynomially in n because there are n² possible pairs in a list of n distinct friends and hence the algorithm would have to perform n² comparisons. Actually, there are n(n - 1)/2 possible pairs. The algorithm is still said to scale polynomially in n, since n(n - 1)/2 = 1/2(n² - n) is a polynomial of degree 2, but I was careless about the details.

Figuring out such details is the subject matter of an area of mathematics called combinatorics, which is the source of many important tools for analyzing algorithms. I’ll give you a little taste of combinatorics by proving that there are n(n - 1)/2 possible pairs of distinct items in a list of n items.

Let’s enumerate the possibilities one item at a time. Consider the first item in the list. There are n - 1 items we can choose to pair with this first item since it can’t pair with itself. The resulting n - 1 pairs account for all pairs that include the first item, so we can leave this item out in considering the remaining possibilities. Now consider the second item. There are n - 2 ways of pairing this item with the remaining items and now we can ignore the second item. Continuing in this manner, we see that the total number of pairs is (n - 1) + (n - 2) + ... + 1 + 0 = ∑_i=1ⁿ(n - i) or ∑_i=1^n-1i.

Well, that’s wonderful to know, but it doesn’t prove what we set out to prove. However, you might recall from Chapter 2 that ∑_i=1ⁿi = n(n + 1)/2. Using this equality, we see that ∑_i=1^n-1i simplifies to n(n - 1)/2. Unfortunately, we didn’t offer any proofs in Chapter 2 and so we’re not much better off than we were before. To make sure that we don’t leave any loose ends, we have to prove that ∑_i=1ⁿi = n(n + 1)/2. We’ll begin by assuming that n is an even number. Watch carefully to see where we use this assumption.

By assuming that n is even we were able to divide the list into two smaller lists, each consisting of n/2 items. Now suppose that n is odd and let’s take advantage of the fact that n - 1 is even. Again, watch carefully for where we exploit this assumption to make use of the case we just proved.

That should do it. If you followed all the steps, you should be convinced that there are n(n - 1)/2 pairs of distinct items in a list of n items. And if you like this sort of thing then you’ll probably like combinatorics and analysis of algorithms. This kind of thinking is obviously quite useful if you want to write code that runs fast; it’s also a lot of fun if you like logic, puzzles and mathematics.

We’re giving data structures rather short shrift in this chapter, but the design and use of good data structures is integral to designing good algorithms and we’ll take a close look at some of the most useful data structures in Chapter 13. First, though, let’s look at some things that computers either can’t do very well or can’t do at all.

12.2  Computational limitations

On October 14, 1947, Chuck Yeager, flying an experimental jet aircraft, was the first human to fly faster than the speed of sound. I know this random factoid because I recently watched “The Right Stuff”, a movie about test pilots and the NASA Mercury 7 astronauts based on the book by Tom Wolfe. Yeager broke what at the time was called the sound barrier, believed by some engineers to prevent aircraft from ever flying faster than sound. The sound barrier turned out not to be a fundamental limit, and eventually engineers found a way to overcome the increase in drag and loss of control produced by the shock waves of compressed air an aircraft creates as it approaches the speed of sound. Fundamental limitations do exist, 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. Theoretical computer science and the theory of computational complexityin particular are about understanding and overcoming fundamental computational limitations.

A story in the first chapter of GareyandJohnson79’s Computers and Intractability concerns a programmer who tells his boss 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 with the interesting property 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 intractablein the sense that any algorithm solving one of them will require an amount of time that scales exponentially in the size of the problem.

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 done it yet and that a lot of computer scientists believe it can’t be done. 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 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ödelshowed that any system sufficiently expressive to capture formally the machinery of arithmetic, the rules and definitions that describe numbers and how they must behave, must be incompletein the sense that it contains assertions that can neither be proved nor disproved. The realization that the tools of mathematics were not up to the task of discovering the whole 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 is a mechanical procedure, an algorithm, to let us determine whether a given assertion is decidable, whether it can be proved or not. Alan Turingwas able to show in 1936 that no such mechanical procedure exists (the problem of determining whether an assertion is provable or not is undecidable) and moreover that, 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 given any computer program can determine whether or not it will halt. This is the so-called halting problem. In a formal sense, Turing showed that there are some problems that cannot be solved by any algorithm running on any computer.

Turing also was able to demonstrate the existence of a general-purpose or universal computerthat can solve any problem solvable by a special-purpose computer. Indeed, the idea of a universal computer is not all that difficult for us to comprehend, given our familiarity with modern-day computers. The abstract computer that underlies the von Neumann architecture discussed in Chapter 9 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. Modern-day computers, no matter how much memory (RAM and disk storage) they might have, are not universal computers as defined by Turing.

The word complexity is the the source of much confusion on the part of computer science professionals and dilettantes alike. Its standard dictionary definitions provide little hint of its technical meaning (or meanings). What makes one computer problem more complex than another? One measure of complexity of interest to computer scientists concerns how long a computer takes to solve a particular problem; a related measure concerns how much memory or space is required to solve a particular problem.

Theoretical computer scientists aren’t interested in how fast a program runs on a 1.5 gigahertz Pentium III running Microsoft Windows versus a 1.2 gigahertz PowerPC G4 running Apple OS X. Or in how much time on the clock, or megabytes of RAM, an algorithm takes to complete a task. Like any good mathematician, a theoretical computer scientist abstracts away 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 term in 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 are required to represent a computation’s intermediate and final products. The algorithms for computing the nth term in the Fibonacci sequence used only integers for their intermediate and final results, but other algorithms use more complicated data structures that require significant space overhead.

Computing the nth term in the Fibonacci sequence is an easy problem as computational problems go. I presented an algorithm that runs in time linear in n.⁴ Other problems require time that scales polynomially in the size of the input, which we designate as n in what follows. Polynomial scaling, often called polynomial time, is obviously worse than linear scaling, but for low-order polynomials (polynomials whose biggest exponent, 3 in the polynomial (4 n³ + 2 n² + 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: are there problems that we care about for which the fastest algorithms scale exponentially in n? The answer to this question lies at the heart of the theory of NP-completeness.

Let P be the class of problems that can be computed in polynomial time and NP be the class of problems that can be computed in nondeterministic polynomial time. NP problems have 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 are not known to have polynomial-time solutions; indeed, every known algorithm for these problems runs in time that scales exponentially⁵ in n.

In addition to the fact that the best-known algorithms for NP-complete problems take exponential time, this problem class is interesting for three reasons. First, if you could solve one problem in this class in polynomial time, then you could solve them all in polynomial time. Second, this is about the easiest class one could imagine that is still not 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 a traveling salesmantrying to minimize his travel in calling on his customers. The problem can be described in terms of a set of n cities representing customers’ locations and a table like a bus or train schedule that lists the routes between pairs of these cities and their distances. The problem is to find a tour(a sequence of cities that begins and ends with the same city and visits each city exactly once) whose length (the sum of distances traveled) is minimal.⁶ This problem is important in a wide range of practical situations 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 attributable in no small measure to Stephen Cook, Leonid Levinand Richard Karp, among other pioneering theoretical computer scientists. 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: 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: the classes are distinct and eventually someone will prove it. (By the way, it’s not 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, produced in 1994 a formal proof that stood up to careful scrutiny.) A proof that P ≠ NP will make it easier for the programmer we talked about earlier to convince his boss that he shouldn’t keep working on a polynomial-time algorithm for an NP-complete problem.

If it is determined that P = NP, the repercussions will 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, have we then been 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 ≠ NP or to turn the field topsy-turvy by demonstrating a polynomial-time algorithm for the traveling salesman problem.

Popular accounts of computing have frequently focused on the theory of computing and the scientists who pioneered it. Douglas Hofstadter79’s Gödel, Escher, Bach is a very readable introduction to Gödel’s work and its implications. Alan Turing: The Enigma by Andrew Hodges83 is a wonderful introduction to Turing’s life and work. Martin Davis00 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 Gardner89’s essay on the traveling salesman problem in Gardner’s Whys and Wherefores is a nice introduction to the ins and outs of this problem. ShashaandLazere95’s Out of Their Minds contains a number of interesting biographies of computer scientists, including Steven Cook and Leonid Levin mentioned in this chapter, Donald Knuth, who is responsible for several fundamental algorithms as well as one of today’s most powerful typesetting systems, John McCarthy, who coined the term “artificial intelligence”and invented Lisp, and Alan Kay, who developed Smalltalk, one of the first object-oriented programming languages. David Harel00’s book on the limitations of computers is an excellent introduction to the theory of NP-completeness. For an in-depth technical discussion of the broader field of computational complexity suitable for graduate-level study, I recommend the text by Christos Papadimitriou94.

12.3  Theory that matters

Students often ask about the significance of NP-completeness results for practicing software engineers. One response is that the results on computational limitations provide general guidance in how to approach problems much as results on the speed of light guide engineers in building faster computers — you’re unlikely to be able to make information flow faster between the components in a circuit, so think harder about how to make the components smaller and closer together. Algorithm designers faced with a hard problem typically look for approximations rather than wasting their time on exact solutions.

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 they require too much time or space. The computational requirements for these problems increase so rapidly that they will probably outpace anything we can build for longer than we care to wait. Here’s an example.

Suppose you’re trying to design an efficient algorithm to find patterns in human DNA as part of a diagnostic test for a new cancer treatment. And suppose that the best-known algorithm for this pattern-finding problem runs in exponential time. For patterns of size 10, this algorithm currently takes several hours.

For the diagnostic test to be useful in a clinical setting, you need to be able to solve the 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 for the foreseeable future, you’d still have to wait 90 years before your diagnostic test will run quickly enough to help patients.

It should be clear from this example that the fact a problem is NP-complete doesn’t mean that we stop working on it; the programmer’s excuses to his boss were 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’re stuck with. And, 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 with 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 some reasonable time with acceptable error.

Beginning students and experienced practitioners alike often fail to distinguish 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 of little interest to a theoretical computer scientist: it may be hard to find an answer to it, but once you do, then you’re done; the problem is solved.

The traveling salesman problem is really an infinite 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 numbers of cities and the tables used to represent the distances between cities 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, 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: that is, how the best algorithm scales as a function of the size of the hardest possible problem instances. 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 before being asked and then simply trot out the answer when asked for the solution to a particular instance.

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 require exponential time. 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 probably have a much greater practical impact than the incompleteness results of Gödel or the undecidability results of Turing.