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.