2 Minutes with Stephen Cook
February 27, 2013
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, Dr. Cook is the 2012 winner of the Natural Sciences and Engineering Research Council's Herzberg Medal.
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.
Well, I was interested in computers, but computer science departments didn't really exist. So when I went to grad school at Harvard, I was in the mathematics department. I wrote a thesis on the brand new field called computational complexity, which had to do with looking at the number—the amount of resources, time and memory to solve problems. That was a new idea. So I came here, to the University of Toronto, which was a budding, new –brand new–computer science department recruiting some top people. And that's where I've been ever since, where I had this neat idea of introducing the concepts we now call NP completeness. That idea, that paper, turned out to be the thing that has made me famous.
Now of course there are thousands of known NP-complete problems, and they're important enough that the many different fields of computer science have been influenced by the concept. But one of the classical NP- complete problems is the so-called travelling salesman problem.
You're given N cities –N is a large number, a hundred or something like that –and their locations on the map. In what order should he [the travelling salesman] visit the cities in order to minimize the total distance he travels? Now, if N is a hundred, a hundred factorial is such a large number that no conceivable computer could ever consider all 100 factorial orders before the sun turned into a red star. So the mathematical question here that's open is whether every NP problem, the search problem, can be done and actually has a polynomial time solution.
As the P versus NP question. It's wide open, in fact, it is now one of the seven problems posted by the Clay Mathematics Institute Millennium Prize problems, and they're offering $1 million to anyone who can solve any one of the problems. So it seems to be one of the seven important open problems in mathematics now.