### P ≠ NP? It’s bad news for the power of computing

##### August 11, 2010 | Source: New Scientist Physics & Math

Has the biggest question in computer science — “P vs. NP” – been solved by Vinay Deolalikar, a mathematician at Hewlett-Packard Labs? If so, he 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 factorizing 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.

But if Deolalidar is right, it would prove that the two classes P and NP are not identical, and would impose severe limits on what computers can accomplish – implying that many tasks may be fundamentally, irreducibly complex.

## comments 1

August 11, 2010by DCWhatthe

Whoa! This is amazing, if true. Lot of disappointed mathematicians out there, who felt they were just on the verge of solving this riddle.

Can’t wait to see if Vinay’s proof stands up to scrutiny.

What a great time to be alive, ya know?