On August 7th I received an email stating that Vinay Deolalikar from HP labs has proven that P in fact does not equal NP. What does that really mean? In layman terms it checks if a solution to a problem can be efficiently checked by a computer, then the computer can efficiently solve the problem. The problem was introduced by Steve Cook in 1971. In this email it stated: “… And Steve Cook says that it is to be taken seriously”.
Background on P and NP. If they have proved the contrary P = NP. This would basically mean that any and all problems can be solved by a computer deterministically. This means that the toughest encryption algorithm can be solved 100% of the time by a computer and so no ones bank account is safe. By proving P != NP we can safely say that some problems do not have solutions and so we need to find solutions to parts of the problem or an alternative. This is the approach that researchers are already taken assuming that P != NP. Now that Vinay has supposedly proven P != NP we can all rest assured that this is indeed the case and find alternatives to problems that do not have deterministic solutions.
If Steve Cook the discoverer of the problem says that this paper should be taken seriously then the chances are that Vinay probably did prove P != NP. I will read this 100 page paper can be found on scribd (http://www.scribd.com/doc/35539144/pnp12pt) soon. I am putting it off as I have enough papers to read for my masters thesis work.
Thusjanthan