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.