By Geoff Brumfiel
A U.S.-based researcher has claimed to solve the sexiest problem in computer science. On the line are a million-dollar prize, a host of scientific breakthroughs and the secure cryptographic systems used for everything from e-mail to banking.
The 100-plus-paged proof was posted on August 6 and has computer scientists and mathematicians around the world buzzing. "It's definitely an approach that we haven't seen before," says Richard Lipton, a computer scientist at the Georgia Institute of Technology in Atlanta, who dropped everything to take a look at the new paper. "It's complicated and it's not clear that it's going to work. But it's certainly not clear in my mind that it's going to fail."
Vinay Deolalikar, the author of the proof and a researcher at HP Labs--the research arm of computer company Hewlett-Packard--in Palo Alto, Calif., was unavailable for comment. "My email is currently backlogged; please bear with some delays in responding," Deolalikar wrote in an automated response.
The title of Deolalikar's paper is also its principal claim: PNP (P is not equal to NP). P and NP describe two types of problems that computer scientists come across frequently--for example, in database management or route planning. Both contain a large number of elements such as numbers, names or locations.
P problems are generally easy for a computer to solve. Take a company that wants to alphabetize a list of thousands of contacts. Although there are a staggering number of combinations in which the contacts could be arranged, a computer programmed to recognize the alphabet would be able to sort them in a flash.
By contrast, NP problems are those for which a computer can recognize a solution quickly, but may or may not have trouble finding one on its own. Think of a jigsaw puzzle: it takes a long time to assemble, but one can instantly recognize whether it has been put together correctly. In a more realistic context, most internet security is built around NP-type problems in which a cryptographic code is easy to check, but hard to crack.
Researchers have wondered since the 1970s whether P=NP, that is, whether there is a hidden order to NP problems that could make them easy to solve. Going back to the jigsaw metaphor, imagine turning over the puzzle pieces to find that they have been numbered sequentially.
If P=NP, there would be a universal solution to a host of seemingly intractable problems. On the plus side, it would make things that seem computationally impossible, such as understanding how proteins fold, easy to solve. It would also allow optimization of complex processes, such as international shipping. On the downside, if P=NP, "basically all the crypto systems that are used every day would all be broken", Lipton says.
The problem is considered so pressing that the Clay Mathematics Institute in Cambridge, Massachusetts, named it as one of its Millennium Prize Problems. The institute has promised $1 million to whomever can show whether or not P=NP.
For better or worse, the new proof seems to show that the NP problems cannot be solved as easily as those in the P category. Lipton and others are still trying to understand the details of Deolalikar's proof, but it essentially works by applying a type of P equation to an NP problem, then showing that it won't work for deeply mathematical reasons.
This is not the first time that someone has claimed to solve the P and NP dilemma, and some researchers are incredulous. "If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of PNP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000," Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology in Cambridge, wrote on his blog, Shtetl-Optimized. "I was literally willing to bet my house on it," Aaronson says in explanation of his wager. Already Aaronson and others are pointing to potentially fatal flaws in the proof.
Lipton agrees that, given past failures, "a bet against the solution is a pretty good casino bet." But he adds that he thinks that Deolalikar's approach to the problem is thought-provoking. And even if it is wrong, the proof could still lead to the right answer. "I don't think he's wasting anyone's time," he says.