Home › Content

P is not equal to NP?

Mon, 2010-08-09 14:32 - Daniele Binosi
Summary: 

HP Labs' researcher Vinay Deolalikar claims to have solved the problem. His answer is that the two classes do not coincide: P is a proper subset of NP.

On August 6 HP Labs' researcher Vinay Deolalikar sent the following letter to his fellows researchers in HP Labs:

"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
www.hpl.hp.com/personal/Vinay_Deolalikar"

The paper (so far, all the experts who have been asked gave this attempt the highest "apparent" rating they could) is available here (66 pages, pdf)

More discussion at Greg Backer's, Lipton's and Scott Aaronson's blog (who by the way adds an interesting bit at the end of the post). I would however love to see comments also on this web.

Update-I: Dirk Kipton and Ken Regan have written a long post summarizing four possible problems with the proof that have been already identified. Go and check it out here.

Update-II: Several reasons why the proof is wrong are discussed in Scott Aaronson's blog which has links to all relevant postings that can be found on the web.