{"id":1084,"date":"2010-08-07T20:21:15","date_gmt":"2010-08-08T03:21:15","guid":{"rendered":"http:\/\/gregbaker.ca\/blog\/?p=1084"},"modified":"2010-08-10T14:47:58","modified_gmt":"2010-08-10T21:47:58","slug":"p-n-np","status":"publish","type":"post","link":"http:\/\/gregbaker.ca\/blog\/2010\/08\/07\/p-n-np\/","title":{"rendered":"P \u00e2\u2030\u00a0 NP"},"content":{"rendered":"

An email I was recently forwarded (a couple of steps removed) from Vinay Deolalikar<\/a> from HP Labs:<\/p>\n

Dear Fellow Researchers,<\/p>\n

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.<\/p>\n

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.<\/p>\n

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.<\/p>\n

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.<\/p>\n

Comments and suggestions for improvements to the paper are highly welcomed.<\/p><\/blockquote>\n

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.<\/p>\n

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

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

Update: Huh, slashdotted<\/a>. 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<\/a> (whose work was cited by Deolalikar in this paper), Valentine Kabanets<\/a>, or Pavol Hell<\/a> (who also do research in this area).<\/p>\n

Update 08\/09: Richard Lipton<\/a> is posting excellent commentary in his blog<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

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. […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10,12],"tags":[],"class_list":["post-1084","post","type-post","status-publish","format-standard","hentry","category-tech","category-work"],"_links":{"self":[{"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/posts\/1084","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/comments?post=1084"}],"version-history":[{"count":15,"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/posts\/1084\/revisions"}],"predecessor-version":[{"id":1099,"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/posts\/1084\/revisions\/1099"}],"wp:attachment":[{"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/media?parent=1084"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/categories?post=1084"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/gregbaker.ca\/blog\/wp-json\/wp\/v2\/tags?post=1084"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}