P ≠ NP

August 7th, 2010, 8:21 pm PDT by Greg

An email I was recently forwarded (a couple of steps removed) from Vinay Deolalikar from 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.

The paper is about 100 pages, and looks serious (but being a decade away from last thinking about complexity, I am unable to give any more useful evaluation than that). I’ll refrain from posting the paper itself.

Deciding P ≠ NP is a Millennium Prize Problem and I don’t think I’d get much argument to say it is the biggest open problem in computing science.

Update: I see someone else Deolalikar has uploaded the paper. I should point out that in the email thread I got, Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.”

Update: Huh, slashdotted. I think “broke” the story is a little strong, but anyway… any media wanting comment on this story, I’d suggest my colleagues David Mitchell (whose work was cited by Deolalikar in this paper), Valentine Kabanets, or Pavol Hell (who also do research in this area).

Update 08/09: Richard Lipton is posting excellent commentary in his blog.

Posted in Tech, Work | 36 Comments »

36 Responses to “P ≠ NP”

  1. Garth Says:
    August 8th, 2010 at 3:50 pm

    Greg, you made Slashdot. Congrats.

    Garth Shoemaker

  2. Ryan Says:
    August 8th, 2010 at 3:56 pm

    Heads up, you’ve been Slashdotted.

  3. P ≠ NP ? [ Vinay Deolalikar from HP Labs Publishes His Proof to the Web, $1Million Clay Institute Prize May Very Well Await ] | Computational Legal Studies™ Says:
    August 8th, 2010 at 5:16 pm

    […] a Millennium Prize for Mr. Deolalikar. For those interested in additional information, check out Greg Baker’s blog (which broke the […]

  4. New Paper Claims Proof P!=NP | Reflections on Operations Research Says:
    August 8th, 2010 at 5:35 pm

    […] Posted on August 9, 2010 by Patricia Randall Greg Baker has broken the news on his blog of a new 100-page paper from researcher Vinay Deolalikar claiming to prove P≠NP. The paper has […]

  5. P != NP « Stii ce vrei ? Says:
    August 8th, 2010 at 5:51 pm

    […] Here is the link to the paper: P ≠ NP. […]

  6. P NP ? - The Quantum Pontiff Says:
    August 8th, 2010 at 6:31 pm

    […] Deolalikar from HP Labs has announced a possible proof that P does not equal NP: see here. Apparently this a fairly serious attack by a serious researcher (previous attacks have all, […]

  7. Is P vs NP solved? | Mark Proffitt Says:
    August 8th, 2010 at 7:12 pm

    […] Deolalikar from HP Labs claims he may have solved the P vs NP problem proving that P ? NP . It’s literally a million dollar problem. Millennium Prize is offering $1,000,000 for the […]

  8. Quantized Thoughts » Blog Archive » P vs NP finally resolved? Says:
    August 8th, 2010 at 7:48 pm

    […] more details see posts by the Pontiff, Greg Baker, and R J […]

  9. This Week in the Universe: August 3rd – August 9th « The Language of Bad Physics Says:
    August 8th, 2010 at 8:28 pm

    […] the University of Toronto‘s Stephen Cook (who is a real authority here) said (according to Greg Baker): This appears to be a relatively serious claim to have solved P vs […]

  10. 惠普研究员Vinay Deolalikar声称证明P!= NP | 丕子 Says:
    August 8th, 2010 at 9:30 pm

    […] 下面附上Deolalikar的邮件内容： Dear Fellow Researchers, […]

  11. Отблески… » P ≠ NP Says:
    August 8th, 2010 at 11:56 pm

    […] вот реакция. Tags: математика, программирование, университет […]

  12. Pues igual resulta que P ≠ NP… | Gaussianos Says:
    August 9th, 2010 at 3:01 am

    […] envió un mail a Greg Baker (entre otros) comunicando la publicación de su trabajo y el mismo Greg lo ha publicado en su blog. En esa entrada comenta que el trabajo parece ser serio y además reproduce la opinión del […]

  13. A relatively serious proof that P ≠ NP? « Antonio E. Porreca Says:
    August 9th, 2010 at 3:30 am

    […] relatively serious proof that P ≠ NP? The news seem to originate from a post on Greg Baker’s blog. The author of the claimed proof that P ≠ NP is Vinay Deolalikar, […]

  14. 惠普实验室研究员声称证明世纪数学难题P!=NP | SolidLine :: 每天都有新发现 Says:
    August 9th, 2010 at 4:52 am

    […] Baker关于这个证明的博客、 Vinay […]

  15. How to get everyone talking about your research! Says:
    August 9th, 2010 at 6:10 am

    […] Deolalikar’s publication list on DBLP, A Proof That P Is Not Equal To NP? by Lipton and P ≠ NP by […]

  16. Morning Brief: Facebook UK Stats, Droid 2 Ad Appearance, Run Flash on iPhone 4 Says:
    August 9th, 2010 at 6:34 am

    […] claim against him, Jodie Fischer, has issued a public statement.Vinay Deolalikar of HP Labs has released a 100-page paper that may have proved the P != NP, one of the seven almost-unsolvable problems that […]

  17. numerology for Vinay Deolalikar « Ed Peterson's (author of the book "Numerology") numerology blog Says:
    August 9th, 2010 at 7:25 am

    […] a Millennium Prize for Mr. Deolalikar. For those interested in additional information, check out Greg Baker’s blog (which broke the story).  Very […]

  18. Morning Brief: Facebook UK Stats, Droid 2 Ad Aussehen, Run auf Flash iPhone 4 | news Says:
    August 9th, 2010 at 7:26 am

    […] Deolalikar der HP Labs ist freigegeben einen 100-seitigen Papier, das P bewiesen haben können! equals NP, einer der sieben fast […]

  19. Proof That P Is Not Equal To NP? | VOLKAN TUNALI Says:
    August 9th, 2010 at 7:45 am

    […] For a few days, everyone in the field of computer science has been talking about the manuscript P ≠ NP published by Vinay Deolalikar from HP Research Labs on August 6, 2010. The 102-page manuscript on the P versus NP problem has taken so much attention from computer science researchers like Scott Aaronson and Greg Baker. […]

  20. ‘Biggest open computing problem’ said solved by Vinay Deolalikar of HP Labs Says:
    August 9th, 2010 at 8:03 am

    […] are getting riled up on news that a long-ranging computer science quandary, described as possibly the “biggest open problem in computer science,” may have been […]

  21. On Brevity at Imaginary Roots Says:
    August 9th, 2010 at 8:49 am

    […] following with interest the recent developments in the P vs. NP […]

  22. P vs NP « Tai-Chi Policy Says:
    August 9th, 2010 at 9:33 am

    […] August 9, 2010 Posted by taoist in Science and Technology. Tags: Computer Science, Math trackback Solved? The paper hasn’t been peer-reviewed yet, but it’s a serious attempt at the […]

  23. P contro NP | Devid Antonio Filoni Says:
    August 9th, 2010 at 4:58 pm

    […] su ossblog (fonte originale: P ≠ NP) che Vinay Deolalikar ha presentato una dimostrazione del problema “P contro NP“. Si […]

  24. HP Researcher Claims to Crack Compsci Complexity Conundrum | Hot Electronics Trends Says:
    August 9th, 2010 at 5:09 pm

    […] equal to NP,” Deolalikar announced in an e-mail to a group of math professors, which was then posted on Sunday by Greg Baker, a senior lecturer at the British Columbia Simon Fraser […]

  25. Posible solución al problema P vs NP « Series Divergentes Says:
    August 9th, 2010 at 9:26 pm

    […] Matemáticas P vs NP Dejar un comentario Hoy circuló por varios blogs (Greg and Kat, Good Math, Bath Math, Shtetl-Optimized, Gödel’s Lost Letter, Francis the e-mule, etc.) la […]

  26. P≠NP. at webCONSUL Says:
    August 9th, 2010 at 10:56 pm

    […] bei Greg Baker, […]

  27. P≠NP? | Q Says:
    August 10th, 2010 at 12:37 am

    […] (no en el sentit de que sigui correcte o no, encara, sinó en el que mereix una lectura sèria): Greg Baker, Dick Lipton, David Bacon i Scott Aaronson. Si és correcte, el premi és d’un milió de […]

  28. ¿Una prueba de que P≠NP? « :: ZTFNews.org Says:
    August 10th, 2010 at 2:11 am

    […] Greg Baker, P≠NP [7 de agosto de 2010] […]

  29. Chris Alexander - Possible proof emerges that P != NP Says:
    August 10th, 2010 at 3:34 am

    […] Yesterday news emerged of an HP researcher who has claimed that he has proved that P != NP. […]

  30. Pesquisador da HP demonstra possível prova de que P != NP | Pablo Ximenes Says:
    August 10th, 2010 at 4:56 am

    […] http://gregbaker.ca/blog/2010/08/07/p-n-np/ This entry was posted in Ensino, Outros and tagged algoritmos, ciência da computação, Cook, P […]

  31. HP engineer claims to have proven P ≠ NP Says:
    August 10th, 2010 at 5:29 am

    […] engineer claims to have proven P ≠ NP Millennial Prize if it holds up, and solves one of the biggest open compsci math problems existent. If you use an ATM card or engage in E-commerce or basically have any internet passwords….this is […]

  32. Science in the Open » Blog Archive » P ≠ NP and the future of peer review Says:
    August 10th, 2010 at 6:21 am

    […] S. Cook: “This appears to be a relatively serious claim to have solved P vs NP.” (gregbaker.ca) […]

  33. P ≠ NP? | Elias Diab log Says:
    August 10th, 2010 at 8:03 am

    […] was on holidays and when I came back I came across this blog post in slashdot which introduced me to this paper-draft by Vinay Deolalikar, where he claims to have […]

  34. Opposed Systems Design :: P != NP :: August :: 2010 Says:
    August 10th, 2010 at 8:24 am

    […] looks like a serious proof for one of the biggest unsolved problems in mathematics has been presented. It is not yet peer-reviewed, so we’ll see how this turns out, but this is a big […]

  35. P ≠ NP? « The Math Less Traveled Says:
    August 10th, 2010 at 11:39 am

    […] draft of a paper entitled “P ≠ NP”. The mathematics and computer science communities immediately erupted in a frenzy of excitement and […]

  36. HP Labs researcher Vinay Deolalikar proves P != NP (possibly) | LogicHP - HP Laptop Coupons, Deals, Reviews, News, and Forum Says:
    August 10th, 2010 at 1:33 pm

    […] given the $1M prize associated with solving one of the Millennium Problems.Via Slashdot via Greg Baker’s BlogRelated posts:New photo editing programs coming from HP LabsHP Labs to become more cost effective […]