The BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category goes, in this eighth edition, to Stephen A. Cook for his pioneering and most influential work on computational complexity. Cook’s work plays an important role in identifying what computers can and cannot solve efficiently. His concept of “NP-completeness” is considered as one of the fundamental principles in computer science.
In his seminal 1971 paper “The Complexity of Theorem-Proving Procedures,” Cook gave a mathematical meaning to “efficiently computable”: a problem is efficiently computable if it is in the class P of problems computable in deterministic polynomial time. He also gave a mathematical meaning to “efficiently verifiable,” as in polynomial time, once a solution is given. An efficiently verifiable problem, if at all solvable, can be solved with a guess-and-check procedure by first guessing a candidate for a solution (the so-called nondeterministic guessing step), and then verifying efficiently that the guess is indeed a solution (the deterministic polynomial-time checking step). Therefore the class of these problems is referred to as NP for nondeterministic polynomial time.
Cook established the now well-known P versus NP question as to whether or not every decision problem that is efficiently verifiable (in NP) can be made to be efficiently computable (in P) and conjectured (now known as Cook’s hypothesis) that P ≠ NP. The P versus NP question is now one of the seven Millennium Prize Problems.
Stephen Cook showed that there are specific problems within the class NP to which all other problems in NP can be efficiently transformed. These problems are referred to as NP-complete problems. If one NP-complete problem can be solved in polynomial time, then all can. Today there are literally thousands of known NP-complete problems in fields as diverse as biology, physics or economics.