Canadian computer whiz grabs $1M for brain teaser

12 years ago

If you’re looking for a million dollars, University of Toronto professor Dr. Stephen Cook can help you get it – if you can just answer a skill-testing question.

The only catch is the brain teaser has stumped even the even the world’s brightest minds and will likely even cause a supercomputer or two to short circuit.

The question raised by Cook, who teaches computer science and mathematics at U of T, is now one of the seven Millennium Prize Problems in mathematics established by the Clay Mathematics Institute of Cambridge, Mass. Cook’s problem won him $1 million from the institute which was created in 2000 to demonstrate that “the frontier is still open and abounds in important unsolved problems.” The person who solves the problem will get $1 million as well, according to a post in the Natural Science and Engineering Research Council of Canada Web site.

Cook’s question stems from a book he published in 1971 titled The Complexity of Theorem-Proving Procedures which introduced what has become known as the “P versus NP problem.”

Theorem can be applied to computer programming, according to Cook. The P versus NP questions revolves around proving that so-called “NP-complete” 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,” said Cook.

The P versus NP problem also has implications in our daily lives since it is linked directly to the field of encryption which involves things such as securing credit card transactions and Internet transmissions.

So what is the P versus NP problem? The NSERCC has this example:

Imagine a travelling salesman who has to 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,” according to the research council.

Find out more about Cook and the P versus NP problem here