From the algorithms that we use to optimize manufacturing to the cryptography that keeps our personal data secure, computational complexity plays an essential role in modern life. But how can we determine which complex problems are easy for computers to solve, and which are difficult or even impossible? Stephen Cook is the foundational thinker behind this field-defining question.
Cook was an undergraduate at the University of Michigan and earned his PhD in mathematics at Harvard in 1966; his dissertation, on the computational complexity of multiplication, improved an essential algorithm now known as Toom-Cook multiplication. He began his career at the University of California, Berkeley, and since 1970 has been a member of the University of Toronto faculty, where he is now University Professor Emeritus. Cook has trained dozens of graduate students, but his influence extends well beyond those who have studied with him directly: nearly 50 years ago, he introduced a concept known as NP-completeness that revolutionized theoretical computer science.
Leslie Valiant, T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics, describes Cook’s discovery of the NP-completeness phenomenon as “the most significant development in the theory of computing since the work of Alan Turing.” Fittingly, Cook was honored in 1982 with the Turing Award, the most prestigious technical award granted by ACM, the Association for Computing Machinery.
Valiant was in graduate school when Cook’s landmark paper on NP-completeness was published in 1971. The paper’s enormous significance, he says, was immediately recognizable. “We are brought up with the impression that great scientific advances were all made in the past,” Valiant observes. “It made a great impression on me as a graduate student that such a sweeping advance was being made in the present and in front of my eyes.”
For some types of problems—like jigsaw puzzles, or Sudoku—it is very easy to verify a correct solution, but difficult or perhaps impossible to come to that solution through an efficient computational means. Problems that are easy to solve are characterized as class P, while those with solutions that are easy to verify are characterized as class NP; a subset of these, NP-complete problems, appear easier to verify than to solve. Cook’s 1971 paper gave the first examples of NP-complete problems, which have now been identified across many fields—not just in computer science and mathematics, but also in operations research, economics, the physical sciences, and more. His theory of NP-completeness provides a way of distinguishing which tasks are easy to compute, and which are impossibly difficult, giving both a potential explanation of the nature of this phenomenon and also a practical approach for determining whether a particular task is easy or likely to be hard.
Salil Vadhan, Vicky Joseph Professor of Computer Science and Applied Mathematics, notes that NP-completeness is not only one of the most important and generative areas of research in computer science: it is also fundamental to computer science education. “In our introductory course in theoretical computer science, which we require of all computer science concentrators, this is probably the most important concept we teach,” Vadhan says.
Cook’s work on NP-completeness also raises a famous—and unanswered—question known as P vs. NP, which asks: what if these seemingly difficult NP-complete problems turn out to be easy for computers to solve after all, through algorithms that we simply have not yet discovered? If we could prove that this was the case—that P in fact equals NP—this finding would overturn decades of conventional wisdom and have a huge impact on technology and optimization methods. If we could prove the opposite—that P definitively does not equal NP—this would help us identify with greater certainty the fastest possible algorithms for a wide array of problems and strengthen the foundations of key areas of computer science, particularly encryption. “Thanks in large part to the theory of NP-completeness, the P vs. NP question is considered the most important open problem in computer science, and also one of the most important open problems in mathematics,” Vadhan says.
Cook’s contemporaries value both his intellectual tenacity and his kindness and integrity. “Steve is universally admired and respected in the field, in part because he marries his brilliance with humility,” says Harry Lewis, Gordon McKay Professor of Computer Science. He adds, “It is characteristic of Steve not to choose easy problems to work on. He picks the hardest problems there are and doesn’t give up on them. In his first paper on NP-completeness, he dryly observes that it is worth spending some effort on this problem. He is still at it!”
Stephen Cook, for your fundamental work on the theory of NP-completeness, which has shaped the course of research and teaching in theoretical computer science, and for your ongoing exploration of the questions that arise from this theory, which are among the most important in computer science and mathematics today, we are proud to award you the 2020 Centennial Medal.
Read about the 2020 Centennial medalists
Photo by University of Toronto
