Communications of the ACM
P ? Np? It's Bad News For the Power of Computing
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.
From New Scientist
View Full Article
No entries found