I haven't yet had a chance to read/understand the paper, but I'm not aware of anyone who seriously thought that P was equal to NP. A proof of P=NP would have been world-shattering. Proofs of stuff that people already assume are true usually have impact through their novel proof procedures/methods. Here, I would imagine that the main advance of the proof will be to formalize the model, so that people can start making changes to the model & thereby find models where the proof doesn't work. In those models, either things become a lot more interesting, or additional proof methods are required. Rinse & repeat. For example, I'm interested in finding out to what extent quantum computing is covered in these models. At 07:54 PM 8/8/2010, Kerry Mitchell wrote:

Assuming for the moment that the proof holds up, what are the implications of P != NP?

Kerry Mitchell

On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber@gmail.com>wrote:

...

Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP.

Paper at

http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf<http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> http://www.scribd.com/doc/35539144/pnp12pt

Some discussion at

http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np...

including the comment that "the original email he sent out was to very well known complexity theorists at schools like stanford, berkeley, mit, princeton, etc (cook, sisper, vazirani, donaldson, etc)"

Text of his email:

Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.

This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.

Comments and suggestions for improvements to the paper are highly welcomed.

Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs