Before deciding how to tackle a problem, we must first know whether it is solvable within a reasonable length of time. Stephen Cook identified a specific class of problem, termed NP-complete, whose defining trait, as he explained yesterday after being told of the award, is that “if you can show that a problem is NP-complete, then very likely you should give up trying to solve it.”

This wisdom to know when there is no point trying may smack of defeatism, but from a practical standpoint the opposite is true. For, as he says, rather than waste time attempting the impossible, programmers can concentrate on “far more useful strategies, such as seeking out approximate solutions.”

Cook is Professor of Computer Science at the University of Toronto. His nominators describe his contribution as standing alongside Turing’s concept of “computability” as a cornerstone of the mathematical foundations of computing. While Turing defined what computers can and cannot solve, Cook added to the mix the principle of efficiency, so the question became what is or is not efficiently computable.

“There are problems that a computer could feasibly solve, except that it would take until the sun burns out,” Cook points out. “These are problems of the class we call NP. And then we have the class that we call P, which can be solved within an acceptable time frame. The trick is to decide which problems are NP [not efficiently solvable], and which are P [easily solvable].”

'There are problems that a computer could feasibly solve, except that it would take until the sun burns out'

Cook’s central achievement was to identify a sub-class of NP problems which he termed NP-complete, whose distinguishing features are, firstly, that they are the hardest and, secondly, that they are computationally equivalent; i.e., finding an efficient algorithm for one would yield algorithms for all the rest, and not just for the sub-set of NP-complete problems, but for NP problems as a whole.

As the jury remarks, “the concept of ‘NP-completeness’ is considered one of the fundamental principles in computer science.” Today there are literally thousands of known NP-complete problems in fields as diverse as biology, physics, economics, number theory, logic, optimization, etc. One example is the way proteins acquire their three-dimensional structure, a key issue in biology. Another is the famous problem of the traveling salesperson: how to find the most efficient route that he or she should follow to cover multiple destinations.

The definition of NP-complete problems provides important guidelines to scientists and engineers, as well as the computer specialists who have to come up with the algorithms that pursue solutions.

Cook published his most influential paper in 1971, not long after earning his PhD. He started from a specific problem in NP, without any idea of how many such problems might exist. He knew that he had got hold of something “interesting”, as he describes it, but could never have suspected the importance it would attain. Just one year after the paper appeared, another mathematician published a list of some three hundred computationally intractable or NP problems.

Cook’s studies gave rise to what is now considered one of the great open questions in mathematics: “P vs. NP”, included on the seven-strong list of “Millennium Problems” of the Clay Mathematics Institute (United States), each one worth a one-million-dollar prize.

In non-technical terms, “P vs. NP” conjectures whether there may not exist some faster way, some brilliant shortcut, that allows NP problems to be solved. In the case of the traveling salesperson, for instance, the only current means to determine the quickest route is to calculate all possible trajectories. This is an NP problem because the calculations required by a large number of stopping points are so numerous as to render it unsolvable. But, are we truly sure that there is no algorithm that can solve the problem without the need for so much work? That, in essence, is the inquiry launched by “P vs. NP”.

Today, the vast majority of mathematicians believe no such algorithm exists, meaning problems in NP are genuinely unsolvable. In other words, P and NP problems are distinct in their complexity. But no one has proved this, and Cook, for one, believes that “no one will, in the short term at least.”

The NP-complete class of problems that he described are “key” in a very real sense, because in the event that they yielded to algorithmic solution, “then all problems in NP could be easily solved,” explains Cook, “and the classes P and NP would coincide.” Solving just one NP-complete problem would prove that no NP is without solution. But Cook is skeptical. “We believe that P and NP are distinct,” he insists, “and that NP are really difficult.”

The jury echoes this view, when it states that “45 years of combined efforts by computer scientists and mathematicians have not found a single efficient algorithm for any NP-complete problems.

If such an algorithm should appear, the implications are enormous, because Internet security systems, and therefore the whole digital economy, rests on the assumption no one can efficiently break encrypted code in a reasonable amount of time.

Cook declared himself “astonished” and “delighted” by the award. In his long career, he has been fascinated to see how “computer science has advanced in leaps and bounds.”

Bio notes

Stephen Arthur Cook (Buffalo, New York, United States, 1939) holds dual American and Canadian nationality. Son of a mathematician and of a homemaker with two master’s degrees (in English and history), he was initially drawn to the applied side of science. While still a secondary school student he helped Wilson Greatbatch, inventor of the implantable pacemaker, to weld the circuits for the first prototype of the device.

He enrolled in science engineering at the University of Michigan, where his parents had first met, but was soon excelling so much in mathematics that he switched his major, receiving his bachelor’s degree in 1961.

His next move was to Harvard University, to pursue his postgraduate studies. At the time, he recalls, he was not that interested in computer science. “I really didn’t know what I wanted to do; but I put down algebra.” Shortly, however, he discovered Alan Cobham’s papers on computational complexity, and ended up making it the subject of his PhD thesis, addressing the complexity of multiplication.

After four years in the Mathematics Department at Berkeley, in 1970 he joined the Department of Computer Science at the University of Toronto, where he still holds a professorship, and one year later presented his seminal paper on “The Complexity of Theorem Proving Procedures”, at the annual congress of the Special Interest Group on Algorithms and Computational Theory of the Association for Computing Machinery.

About the BBVA Foundation Frontiers of Knowledge Awards

The BBVA Foundation established its Frontiers of Knowledge Awards in 2008 to recognize the authors of outstanding contributions and radical advances in a broad range of scientific, technological and artistic areas congruent with the knowledge map of the late 20th and the 21st centuries, and others that address central challenges, such as climate change and development cooperation, deserving of greater social visibility and recognition.

Their eight categories include classical areas like Basic Sciences and Biomedicine, and other, more recent areas characteristic of our time, ranging from Information and Communication Technologies, Ecology and Conservation Biology, Climate Change and Economics, Finance and Management to Development Cooperation and the innovative realm of artistic creation that is Contemporary Music.

The juries in each category are made up of leading international experts in their respective fields. The BBVA Foundation is aided in the organization of the awards by the Spanish National Research Council (CSIC). As well as designating each jury chair, the CSIC is responsible for appointing the technical evaluation committees that undertake an initial assessment of candidates and draw up a reasoned shortlist for the consideration of the juries.

CSIC technical committee members in the Information and Communication Technologies category were Juan José García Ripoll, Tenured Researcher at the Institute of Fundamental Physics (IFF-CSIC); Manuel Lozano Fantoba, Coordinator of the CSIC Physical Sciences and Technology Area and Research Professor at the Barcelona Microelectronics Institute of the National Microelectronics Center (IMB-CNM-CSIC); Pedro Meseguer González, Research Scientist at the Artificial Intelligence Research Institute (IIIA-CSIC); Salvador Miret Artes, Research Professor at the Institute of Fundamental Physics (IFF-CSIC); and Carmen Torras Genis, Research Professor at the Institute of Robotics and Applied Informatics (IRII-CSIC).

Information and Communication Technologies jury

The jury in this category was chaired by George Gottlob, Professor of Computer Science at the University of Oxford (United Kingdom), with Ramón López de Mántaras, Director of the Artificial Intelligence Research Institute of the Spanish National Research Council (CSIC) acting as secretary. Remaining members were Oussama Khatib, Director of the Robotics Laboratory and Professor of Computer Science at Stanford University (United States), Rudolf Kruse, professor of the Faculty of Computer Science at the University of Magdeburg (Germany), Mateo Valero, Director of the Barcelona Supercomputing Center (Spain), and Joos Vandewalle, Head of the SCD Division of the Department of Electrical Engineering at KU Leuven (Belgium).