The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Stephen A. Cook

Born 14 December 1939, Buffalo, New York, USA

ACM A.M. Turing Award (1982) “for his advancement of our understanding of the complexity of computation in a significant and profound way. His seminal paper, ‘The Complexity of Theorem Proving Procedures,’ presented at the 1971 ACM SIGACT Symposium on the Theory of Computing, laid the foundations for the theory of NP-completeness. The ensuing exploration of the boundaries and nature of the NP-complete class of problems has been one of the most active and important research activities in computer science for the last decade.”

Cook’s father was a chemist and his mother was an English teacher. He was interested in electronics from his teens and studied at the University of Michigan from 1957. He enrolled at first in Science Engineering, but changed his interests focusing later on Mathematics (Bachelor of Science 1961). Afterwards he went to Harvard University (Scientiæ Magister 1962, Ph.D. 1966) where he was in particular interested in computational complexity, which was at that time still in its infancy. His doctoral thesis ‘On the Minimum Computation Time of Functions’ dealt with the complexity of algorithms for multiplication.

Afterwards he worked as an assistant professor in Computer Science at the University of California, Berkeley (1966-1970) and the University of Toronto, Canada (1970-1975), where he became professor in 1975. In 1985 he received the honorary title University Professor.

Cook is a Fellow of a great number of research institutions. Among his many accolades, he also received the CRM-Fields-PIMS Prize (1999) and the Gerhard Herzberg Canada Gold Medal for Science and Engineering (2013) which comes with a research budget of one million dollars. Stephen Cook enjoys sail boat racing and playing the violin. He is married and has two sons.

The concept of NP-completeness, one of Cook’s ideas from the beginning of the 1970s, has a long history. In 1936 Alan Turing published his idea of the ‘Turing machine’, a kind of standard method of formulating computer programs. About 30 years later the mathematician Jack Edmonds set out to compare algorithms by counting the steps necessary to solve problems on a Turing machine – problems such as sorting numbers or finding the shortest round path through cities on a map. Of course, it takes longer to sort 100 numbers than to sort only 10; one speaks of different sized ‘instances’ of the same problem. Edmonds found it acceptable if the running time does not exceed a certain rate of growth when growing with the size of the instances.

Stephen Cook focused on the decision of a problem, that is problems which can be answered with yes or no. For example: A street map has a certain number of cities. Is it possible to drive through each of these cities exactly once, using no street twice, on a tour that is shorter than a certain length? Obviously, one can easily – in Edmonds’ sense – check if a given route is in fact a true round trip and if it is shorter than the given length. But Cook – and independently also the soviet mathematician Leonid Levin – proved even more. They showed a way in which many problems are equivalent in their complexity to a certain reference problem, called SAT. One of these problems is the task to actually find the shortest round trip on a street map. Today, we know thousands of those problems, for which alleged solutions can be tested quickly, but actually solving them is equivalent to the solution of SAT; this is the class of NP-complete problems. For no problem in this class, do we know a fast method to find a solution. Is it theoretically impossible? That is one of the key questions of modern mathematics, is P ≠ NP?