A quick and technically indefensible summary of the P-versus-NP problem: Quick --- what are the factors of 477310661? That looks like a hard problem. But if I tell you that 477310661 = 17389 x 27449, then it's easy to check me. A problem is called "P" if it's easy to find solutions, and "NP" if it's easy to check solutions. These categorizations apply not to specific problems like "Factor 477310661" but to general problems like "Factor any number I happen to give you". We strongly suspect that the problem of factoring is not P. That is, we strongly suspect that there is no easy way to factor numbers. Of course, we might be wrong. Maybe there's an easy method we just haven't thought of yet. We are quite sure that the problem of factoring is NP, because it's that you can easily check a solution simply by multiplying. The P-versus-NP problem asks: Is every NP problem also P? If the answer is yes, then factoring, being NP, must also be P, so --- contrary to our expectations --- there must be some easy way to factor. And there must be easy ways to solve every other NP problem in the world. That seems pretty unlikely. What Deolalikar claims to have proved is that the answer is no --- P does not equal NP. That means some problems have solutions that are easy to check and hard to find, just as we suspected all along. But settling this question for certain has been the central problem in theoretical computer science for decades.