P .NE. NP proof?

If you don’t understand the heading, don’t bother.

One of the great unsolved propositions in Computer Science, known as “P equals NP,” may have been solved. Vinay Deolalikar at HP labs claims on his site:

P is not equal to NP. 6th August, 2010 (66 pages 10pt, 102 pages 12pt). Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. Final version of the paper to be posted here shortly. Stay tuned.

It might be a hoax, and the proof may have holes, but it seems by all accounts to be a genuine attempt at a proof, from someone who certainly knows his stuff.

The first draft of the paper is on Scribd.

For a layman’s description of P = NP, see the Wikipedia article.