Past Winner
2012 NSERC Gerhard Herzberg Canada Gold Medal for Science and Engineering

Stephen Cook

Computer Science and Mathematics

University of Toronto

Stephen Cook

Mathematics research, at its most fundamental level, strives to understand what can be known and proven true. Breakthroughs in the field are rare and often open entirely new avenues of research.

Stephen Cook is among a short list of mathematics researchers whose ideas have spawned new fields of inquiry for current and future generations. A professor of Computer Science and Mathematics at the University of Toronto, Cook is the 2012 winner of the Natural Sciences and Engineering Research Council’s Herzberg Medal.

Dr. Cook’s 1971 paper “The complexity of theorem–proving procedures” gave mathematical meaning to “efficiently computable” and “efficiently provable.” He identified a large class of important problems that appear to be computationally intractable, but a tractable algorithm for any one of them would yield tractable algorithms for all of them.

For example, imagine a travelling salesman must visit 100 cities located across the country. In what order would he have to visit the cities to have the shortest trip possible? The potential number of routes the salesman could take is so numerous that no computer could determine the answer in our lifetime. The basic question then becomes, does every mathematical problem like the travelling salesman question, which is computationally intractable, have a solution that will allow it to be computed in an efficient amount of time?

Dr. Cook’s research has had a lasting impact in the field of computer science. He received an A.M. Turing Award for his work, the highest honour for a researcher in computer science, and his inquiries are now among the essential theoretical results that all computer science graduates must understand. The basic question he raised is now among the seven Millennium Prize Problems in mathematics, solutions to which are each worth US$1 million.

In addition to celebrated contributions to complexity theory, Dr. Cook has made fundamental contributions to computational theory, algorithm design, programming languages and mathematical logic, and his still-growing body of work is likely to be cited for many decades to come. His work has made an impact on various areas of mathematics and computation, and a contribution to many other fields of research.