The problem of proving that P is not equal to NP is probably the most important and well known problem in computer science. (See the Related Reading section for articles on what NP and P are all about.)

Now Vinay Deolalikar, a well known researcher in networks and complexity theory from HP Labs, has produced a paper that claims to prove P does not equal NP. If nothing else the solution to the problem is big news because it is one of the Millennium Prize Problems and hence associated with a one million dollar prize for the person who solves it.

Deolaliker worked on the problem in his spare time and when he finally made his "breakthrough" he sent the paper as an email to a number of different "leading researchers"  in various areas. The news was made public in an informal blog and the paper was published on the web, apparently without Deolalikar's knowledge. You can read the paper following the link below.

Of course most computer scientists have long believed that NP was different from P - it just seems reasonable that it should be so. However, in the past long held "beliefs" have been overturned when a real proof was discovered and so there was, and perhaps still is, the nagging doubt that NP and P might be the same. If this was so then the effects might be serious as most codes are based on the distinction.

Currently the status of the paper is not settled - is it a proof or does it contain a flaw. Normally this sort of question is settled by peer review and this can take time. The Internet has speeded things up but it has also made it more difficult to know when an erroneous, or even a crackpot, proof is being hailed as the solution to some prestigious problems.

In this case the author has a suitable track record. Along with other researchers, he proved that P was smaller than NP for infinite time Turing Machines. This reduces the chances that the paper is spurious,  but it will still be some time before a final verdict is reached.

The most academically reliable discussion of the paper can be found on Prof. Richard Lipton's blog A Proof That P Is Not Equal To NP?

Deolaliker states that a final version of the paper will be available on his web page in about a week.

At the moment the early draft can be read at pnp12pt.pdf

Further Reading

Computational Complexity

Computability

<ASIN:0521424267>

<ASIN:0262033844>

<ASIN:0716710455>

<ASIN:0201000237>

<ASIN:0805071660>