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.
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.