Natural Sciences and Engineering Research Council of Canada
Symbol of the Government of Canada

A Million Dollar Question

Stephen Cook could help you win one million dollars. To collect, you just have to answer a skill-testing question. Problem is: the best minds in mathematics have so far been unable to do it.

In 1971, Dr. Cook published The Complexity of Theorem-Proving Procedures, which introduced what has come to be known as the “P versus NP problem.” Here’s an 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? 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, is there a solution for every mathematical problem like the travelling salesman question that will allow it to be computed in a shorter, more feasible, amount of time?

The question raised by the University of Toronto professor of computer science and mathematics is now one of the seven Millennium Prize Problems in mathematics established by the Clay Institute, each worth one million dollars.

Besides capturing the imagination, the problem proposed by Dr. Cook significantly advanced the field of mathematics and computation. Mathematics research, at its most fundamental level, strives to understand what can be known and proven true.

The P versus NP question revolves around proving that the so-called “NP-complete” problems cannot be solved exactly by computers. “Practical computer programmers are often skeptical of such impossibility proofs, but the lesson is that compromises are sometimes necessary in designing programs,” says Dr. Cook.

His work has direct implications in most people’s daily lives. The P versus NP problem is directly tied to the field of encryption, which, among other things, ensures credit cards can be used securely over the Internet. Dr. Cook has also made fundamental contributions to computational theory, algorithm design, programming languages and mathematical logic. His still-growing body of work is likely to be cited for many decades to come, and contributes to many other fields of research.

Dr. Cook, the 2012 winner of the NSERC Herzberg Medal, has achieved a number of significant breakthroughs in his field and has opened entirely new avenues of research and inquiry. Questions he has raised are now among the most essential theoretical results that all computer science graduates must understand. He has received the A.M. Turing Award from the Association for Computing Machinery for his work, the highest honour in computer science.

“The Herzberg Medal is a great honour and a privilege, but most satisfying is that it provides resources that will help our entire research group at the University of Toronto to continue making a positive impact,” says Dr. Cook.

Watch a video of Stephen Cook discussing his research.

People Discovery Innovation