Researcher claims to have solved the biggest problem in computer science.
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: P?NP (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.
