University of Toronto researcher collects prestigious science prize

The Canadian Press / Times Colonist
February 27, 2013

OTTAWA - A Toronto researcher with a million-dollar question has been awarded the country's highest science research honour.

Stephen Cook, a University of Toronto mathematician and computer scientist will receive $1 million in research funding over the next five years as the recipient of the Herzberg Gold Medal from the Natural Sciences and Engineering Research Council of Canada.

Cook has made key contributions to computational theory, algorithm design, programming languages and mathematical logic. His research is among the essential theoretical results in computer science.

He is also noted for posing a question so difficult to solve that whoever comes up with the solution will receive $1 million.

Cook's question, known as the "P versus NP problem," is one of seven Millennium Prize Problems in math established by the Clay Mathematics Institute of Cambridge, Mass.

Announced in 2000, only one of the seven has been solved so far.

Cook's question searches for a solution to certain mathematical problems that would allow it to be computed in a reasonable amount of time.

The research council gives this example: "Imagine a travelling salesman who must visit 100 cities located across the country. In what order would he have to visit the cities to make the shortest trip possible?"

It says that there are so many potential routes that no computer could determine the answer in our lifetime.

The council says Cook's work on the "P versus NP problem" is directly tied to the field of encryption and ensures credit cards can be used securely online.

Prizes for top graduate students were also to be awarded by the council in a ceremony hosted Wednesday by Gov.-Gen. David Johnston.

The Natural Sciences and Engineering Research Council of Canada supports almost 30,000 post-secondary students and postdoctoral fellows in their studies.