Skip to main content

Stephen Cook, professor of computer science and mathematics at the University of Toronto.

Kevin Van Paassen/The Globe and Mail

In 1971, Dr. Stephen Cook, a young University of Toronto professor in the fledgling field of computer science, posed a theoretical problem so intractable it has become the subject of a $1-million prize. Since then, only a handful of credible solutions have been posed. All of them fell short. This month, one man caused a commotion after he announced to experts in the field that he had solved the problem known as P vs. NP.

The proof

Vinay Deolalikar, a Delhi-born mathematician at Hewlett-Packard, sent Dr. Cook and two dozen other experts in the field an e-mail, writing, "I am pleased to announce a proof that P is not equal to NP, which is attached." The paper was more than 100 pages long. Dr. Cook was excited. In 40 years, "I can think of only a couple of other attempts of people who've thought they've proved it," Dr. Cook said. "Most of them you can dismiss very easily - they're not really mathematicians. But this one was much more serious."

Story continues below advertisement

The problem

Clay Mathematics Institute, the Cambridge, Mass.-based academy that offers the $1-million prize, describes the problem with this example: Imagine you are trying to figure out housing for 400 university students. Only 100 will get rooms, and the dean has given you pairs of incompatible students she doesn't want living together. The number of ways to choose 100 students out of the 400 applicants is greater than the number of all the atoms in the universe, and no known supercomputer can solve it. But any list you do devise will be simple to check by making sure no incompatible student pairs appear on it.

This type of question is known as P vs. NP, computer programming-speak for "easy to find" versus "easy to check." In a nutshell, it asks: Are there problems for which an answer is impossible to generate through computing, but for which an answer, if given, is easily checkable? Proofs have been offered on either side - the P does equal NP, and that P does not equal NP - but none in 40 years have stuck.

The stakes

P vs. NP may be the holy grail of a theoretical field, but it has enormous practical implications. When a consumer buys a product over the Internet using a credit card, that transaction is secured with a seemingly unbreakable mass of coding. "The security assumption is based on an unproven fact that no computer can do it," Dr. Cook explains. Modern-day cryptography rests on the same assumption. Anyone who proves that P does equal NP would undermine the foundations of code-breaking, e-commerce and digital privacy.

The prof

As a math graduate student at Harvard in the 1960s, Dr. Cook became interested in the fledgling field of computer science. "There was a huge amount of interest in what [computers]can do and can't do," he says. When the University of Toronto inaugurated one of the first computer-science departments in the world, Dr. Cook moved north, and soon after, in 1971, he formulated P vs. NP. He has been teaching and studying computational complexity at the university ever since. Among other accolades, he won the 1982 Turing Award, considered the Nobel Prize of computer science.

Story continues below advertisement

The prize

In 2000, the Clay Mathematics Institute chose seven of the longest-standing math problems and dubbed them "millennium problems." Each comes with a $1-million prize. One was P vs. NP, and another, the Riemann Hypothesis, was formulated in 1859. A third, the Poincaré Conjecture, was famously solved in 2003 by Grigoriy Perelman, an elusive Russian mathematician who turned down his cash prize in July.

The unravelling

After the initial commotion over Mr. Deolalikar's paper died, Dr. Cook and other experts took a crack at the proof. Problems began to emerge. "As I looked at it more, I could see that it had symptoms that didn't make it look too promising," Dr. Cook said. Other professors put the problem up on blogs, and one wiki created by quantum physicist Michael Nielsen. On Aug. 13, computer scientist Scott Aaronson, who had bet $200,000 the proof wouldn't fly, wrote on his blog that "a clear consensus has emerged that the proof, as it stands, is fatally flawed."

Mr. Deolalikar has submitted a revised proof, but Dr. Cook believes the jig is up. Does he believe P vs. NP will ever be solved? "Yes, I do, I do - eventually. But not very soon. I think it really is a hard problem. It's becoming increasingly clear, because so many top mathematicians have tried to solve it."

Report an error Editorial code of conduct
Comments

Welcome to The Globe and Mail’s comment community. This is a space where subscribers can engage with each other and Globe staff. Non-subscribers can read and sort comments but will not be able to engage with them in any way. Click here to subscribe.

If you would like to write a letter to the editor, please forward it to letters@globeandmail.com. Readers can also interact with The Globe on Facebook and Twitter .

Welcome to The Globe and Mail’s comment community. This is a space where subscribers can engage with each other and Globe staff. Non-subscribers can read and sort comments but will not be able to engage with them in any way. Click here to subscribe.

If you would like to write a letter to the editor, please forward it to letters@globeandmail.com. Readers can also interact with The Globe on Facebook and Twitter .

Welcome to The Globe and Mail’s comment community. This is a space where subscribers can engage with each other and Globe staff.

We aim to create a safe and valuable space for discussion and debate. That means:

  • All comments will be reviewed by one or more moderators before being posted to the site. This should only take a few moments.
  • Treat others as you wish to be treated
  • Criticize ideas, not people
  • Stay on topic
  • Avoid the use of toxic and offensive language
  • Flag bad behaviour

Comments that violate our community guidelines will be removed. Commenters who repeatedly violate community guidelines may be suspended, causing them to temporarily lose their ability to engage with comments.

Read our community guidelines here

Discussion loading ...

Due to technical reasons, we have temporarily removed commenting from our articles. We hope to have this fixed soon. Thank you for your patience. If you are looking to give feedback on our new site, please send it along to feedback@globeandmail.com. If you want to write a letter to the editor, please forward to letters@globeandmail.com.
Cannabis pro newsletter