# The Million Dollar Problem

Rob Hardy

Everyone knows that computers are getting more powerful and better at doing almost anything. Finding you the fastest route cross country is easy. Translating a page of prose from one language to another is harder, but it's getting better all the time. Finding the shortest route that will get you to all of five different cities, no problem; finding the provably shortest route that will get you to all of a thousand cities - that's a toughie. It's so hard that perhaps no computer, no matter how big or how fast, can ever do it. Perhaps. Are there tasks beyond computing? It is a deep question bridging mathematics and computer science, and it is the subject of The Golden Ticket: P, NP, and the Search for the Impossible (Princeton University Press) by Lance Fortnow. The question is so hard, and so important, that it is one of the seven Millennium Problems for which the Clay Mathematics Institute will give you one million dollars when you prove it. (Programming genius Donald Knuth will also give you a turkey.) This is deeper mathematical territory than most of us will ever penetrate, but Fortnow, a professor of computer science, keeps the explanations light, knowing that those of us reading this sort of book aren't really in the running for the prize, but at the same time showing how important the answer to the question might be for the future of computing.

It is best to call it the P/NP problem; the abbreviation P comes from "polynomial;" and in giving us the second, Fortnow jokes, "NP (which stands for 'nondeterministic polynomial time,' if you really need to know)." He does not get much deeper into polynomials, but P is the group of problems we know computers can solve quickly. NP is a possibly separate group of problems that cannot be solved quickly by any computer program we have now, but if P = NP, then a powerful computer could solve those NP problems as easily as computers are currently solving the P ones. It would be very nice if P = NP, because then we could expect efficient algorithms that would do all the problems we now think of as NP. Fortnow's second chapter imagines a world where P = NP: cancer prediction and treatment all come from a simple blood draw, weather is predicted accurately a year in advance, and Schubert's Eighth Symphony is finally completed. It's not all good news: the public-key cryptography we all now use for electronic financial transactions would be easily cracked, and there would be tremendous losses of jobs because of all the new stuff computers could do.

The programs for these intricate problems would still have to be written, but if P = NP, they could be written, and undoubtedly would be. One of the important parts of Fortnow's book is that he shows that the P/NP problem is not something just of interest to mathematicians and computer scientists. It is a critical question in fields as diverse as biology, economics, medicine, and physics. Kurt Gödel famously showed that there are mathematical truths that cannot be proved even though they are true; now can someone show in some similar way that NP problems really are different from P? One chapter here gives the history of the problem, a history bifurcated because of the Cold War in the seventies. The problem was first defined in the West in 1971; Russian mathematics at the time was dragged down by strong central politics within the Russian mathematical community, but eventually P/NP became a worthy subject of research there as well. Mathematicians on both sides are now doing research on the problem, but not in the sort of isolation that used to be; the collapse of the Soviet Union and the worldwide reach of the internet have meant that solving P/NP is a globally communal quest.

A good example of what we know to be an NP problem is the Traveling Salesman Problem, the one about getting the absolute minimum travel distance for a salesman who wants to visit a hundred cities, or a thousand, or a million. If you only want to go to the 48 state capitals in the lower US, you could have a computer look at lists of cities in every order and total up the mileage, but there are so many possible orderings that the fastest of computers would take longer than the age of the universe to solve the problem. Programmers do solve versions of the Traveling Salesman Problem, but they do so by approximation; they cannot be sure if the answer they get is the real minimum distance or just very close to it. This is the same sort of issue with problems having to do with protein folding in biology or finding minimal energy states in physics, and if one of these NP problems can be shown to be P, then all the rest of them are P, too, and our computers can grind out answers to all NP problems efficiently.

No one has been able to come up with an efficient algorithm that solves any NP problem, which seems to indicate there is no such thing, and that P is not equal to NP. It would be a real surprise if P = NP, but right now there is no proof either way. There are plenty of people working on it. Some of them are the same sort of people who are sure they have proved the classic (and unprovable) problem of trisecting an angle. One computer journal has ruled that it will accept such P/NP proofs from any one author no more often than every two years, because most such attempts are "unreadable or clearly wrong." Fortnow encourages readers to try proving P/NP, "for you cannot truly understand the difficulty of a problem without attempting to solve it," and while his book does not give formal definitions of P/NP that would be the basis for your proof, it has website citations that could start you off. But on the other hand: "Suppose you have actually found a solution to the P versus NP problem," he writes. "How do you get your \$1 million check from the Clay Mathematics Institute? Slow down. You almost surely don't have a proof. Realize why your proof doesn't work, and you will have obtained enlightenment."

Not only are you unlikely to get a proof, Fortnow is pessimistic that any mathematician is going to be coming up with one anytime soon. He knows the state of current research on the problem, and says that there is no known line of attack currently being pursued that could lead to a successful proof. Things seem to be at a standstill. He reminds us that it took 357 years to get a proof of Fermat's Last Theorem. While we may continue to butt our heads up against NP problems with merely approximate answers, and while P will increasingly seem not to equal NP, there may be no proof out there ever. Fortnow's book does a fine job of showing why the tantalizing question is an important one, with implications far beyond just computer science.