New Scientist | Physics & Math | 10 Aug 2010
Has the Devilish Math Problem “P vs NP” Finally Been Solved?Has the biggest question in computer science been solved? On 6 August, Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California, sent out draft copies of a paper titled simply "P ≠ NP".
This terse assertion could have profound implications for the ability of computers to solve many kinds of problem. It also answers one of the Clay Mathematics Institute's seven Millennium Prize problems, so if it turns out to be correct Deolalikar will have earned himself a prize of $1 million.
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.
So if P = NP, every problem that can be checked quickly can also be completed quickly. That outcome would have huge repercussions for internet security, where the difficulty of factorising very large numbers is the primary means by which our data is kept safe from hackers.
...
Complexity theorists have given a favourable reception to Deolalikar's draft paper, but when the final version is released in a week's time the process of checking it will intensify.
Discover Blogs | 80beats | 10 Aug 2010
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:
That definition is pretty abstract, so here’s a more concrete example:
- 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].
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 not equal 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.
- 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].
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.
- 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].
In the days since the proof began to spread across the Internet, however, some math bloggers like Scott Aaronson have responded to the proof by saying yes, it’s lovely, but no, it probably isn’t going to stand.
