P versus NP, that is the question

The problem in question, P versus NP, turns on what a computer can solve in an efficient manner. Cook first formulated it in 1971. Back then the computer age was in its infancy, and the value of Cook’s contribution was not easily appreciable.

But just one year later, another mathematician published a list of dozens of problems that, in practice, are beyond the reach of computers at the current state of knowledge. And their number was a lot larger than expected. Thus began the fame of Stephen Cook’s P versus NP.

The list of problems not solvable within a reasonable time has lengthened with the years, and P versus NP has become the Excalibur which every mathematical genius has at some time grappled with. As to Stephen A. Cook (Buffalo, United States, 1939), he is currently Professor of Computer Science at the University of Toronto, and the latest winner of the BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category “for his pioneering and most influential work on computational complexity.”

As a child, Cook did not know any mathematicians and, he admits, had “no idea what they actually did.” He had, however, taken a teenage summer job with the inventor of the implantable cardiac pacemaker, Wilson Greatbach, who lived in his home town. Encouraged by this experience and his curiosity about the new transistors appearing on the market, he enrolled for an engineering degree at the University of Michigan.

A professor there spotted his ability and won him over to mathematics. After completing a PhD at Harvard, in 1966, he began working in computer science, an area that mathematicians, Cook recalls, “still didn’t consider quite respectable mathematically speaking.”

This may be the reason why the Mathematics Department of the University of California, Berkeley, where Cook had been teaching for four years, failed to offer him a stable position. Richard Karp, of Berkeley’s Computer Science Department, has since written: “It is to our everlasting shame that we were unable to persuade the math department [to give him tenure].” In 1970, Cook accepted an offer from the University of Toronto.

At that time “computers were relatively new, and it seemed natural to study which kinds of problems they could solve efficiently,” says Cook on the subject of why he chose his area of research. The efficiency issue is important. Many years earlier, Alan Turing had defined what computers can and cannot solve, in absolute terms. But it transpires that “there are problems that a computer could feasibly solve, except that it would take until the sun burns out,” Cook points out.

These effectively unsolvable problems exist in biology, physics, economics, etc., and it is important to identify them so as not to “waste time” trying to solve the unsolvable, and instead concentrate on finding what Cook calls “approximate but useful solutions.”

Nowadays there is no doubting the admiration that mathematicians and computing experts feel for the father of P versus NP, one of the seven Millennium Problems for whose solution the Clay Mathematics Institute (United States) has offered a one-million-dollar prize.

NP problems – the letters stand for non-deterministic polynomial time – are those which cannot be efficiently solved, while P problems can. An example of an NP problem is the case of the traveling salesman: how to find the most efficient route that he should follow to cover multiple destinations. What sets them apart is that the right answer can only be arrived at by testing all the options, a task that could take even the most powerful computer billions of years.

But is there truly no algorithm that can solve the problem without all these calculations? Is there no brilliant shortcut that can make NP problems yield to a solution? This precisely is the conjecture posed by P versus NP. The answer, as we write, is a firm “don’t know.” It is possible that NP problems may actually be P problems in disguise, i.e., efficiently solvable problems for which no one has yet worked out a suitable line of attack.

Cook’s central achievement was to identify a sub-class of NP problems which he termed NP-complete. These are “key” problems, because solving one of them efficiently would mean all NP problems lend themselves to efficient solution. Conversely, if it can be shown that there is no way to solve an NP-complete problem in a manageable time, then the door between P and NP will stay locked forever.

Cook favors the latter option; that P and NP are not the same. What he likes most about mathematics is “the idea that you can prove a precise statement to be true, and there can be no rational argument challenging its truth.” But, for the time being, he will have to live with the fact that Cook’s conjecture inhabits the limbo of the yet unproven.