Sign In

Communications of the ACM

ACM News

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

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Read CACM in a free mobile app!
Access the latest issue, plus archived issues and more
ACM Logo
  • ACM CACM apps available for iPad, iPhone and iPod Touch, and Android platforms
  • ACM Digital Library apps available for iOS, Android, and Windows devices
  • Download an app and sign in to it with your ACM Web Account
Find the app for your mobile device
ACM DL Logo