Go to the Globe and Mail homepage

Jump to main navigationJump to main content

Stephen Cook, professor of computer science and mathematics at the University of Toronto. (Kevin Van Paassen/The Globe and Mail)
Stephen Cook, professor of computer science and mathematics at the University of Toronto. (Kevin Van Paassen/The Globe and Mail)

The problem of P versus NP Add to ...

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

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.

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

 

In the know

Most popular videos »

Highlights

More from The Globe and Mail

Most popular