Has the Devilish Math Problem “P vs NP” Finally Been Solved?

P is not equal to NP. Seems simple enough. But if it’s true, it could be the answer to a problem computer scientists have wrestled for decades.

Vinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. Mathematicians are reviewing his work now—a task that could go on for a long time. If he’s correct, Deolalikar will have figured out one of the Clay Mathematics Institute’s seven Millennium Prize Problems, for which they give $1 million prizes. (Grigory Perelman won one of the seven for solving the Poincaré conjecture, but turned down the money last month.)

What’s all the hubbub? First, an explainer:

The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P. If the answer to a task can be checked quickly then it is in class NP [New Scientist].

That definition is pretty abstract, so here’s a more concrete example:

Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large — more than the total number of atoms in the universe — but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean’s prohibited pairs is on the list, that’s an error [AOL News].

Thus, if P were equal to NP, it would mean that problems that are easy to check—like this roommate match-up—must also be easy to solve. But if Deolalikar is correct and in fact P is notequal to NP, as many mathematicians already believed, then that ain’t necessarily so. And that would have practical meaning, according to Michael Sipser of MIT.

Sipser … says that the P-versus-NP problem is important for deepening our understanding of computational complexity. “A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says [MIT News].

Deolalikar’s proof is now available to read online. New Scientist and Network World report that he pulled together tactics from different disciplines to show that an NP problem—whether a list of statements can be simultaneously correct or contradict one another—is not a P problem, because it can be easily checked but no computer can figure it out quickly from scratch.

In the days since the proof began to spread across the Internet, however, some math bloggers likeScott Aaronson have responded to the proof by saying yes, it’s lovely, but no, it probably isn’t going to stand.