{"id":1888,"date":"2010-08-09T01:52:59","date_gmt":"2010-08-09T08:52:59","guid":{"rendered":"http:\/\/arcanius.silverfir.net\/blog\/?p=1888"},"modified":"2010-08-10T06:27:52","modified_gmt":"2010-08-10T13:27:52","slug":"n-np-problem-solved","status":"publish","type":"post","link":"https:\/\/arcanius.silverfir.net\/blog\/n-np-problem-solved\/","title":{"rendered":"P = NP problem solved?"},"content":{"rendered":"<p>Pretty big news breaking today about a possible breakthrough on the <a href=\"http:\/\/en.wikipedia.org\/wiki\/P_versus_NP_problem\">P vs NP problem<\/a>, probably the most important unsolved problem in computer science today. Everyone suspects, to a degree bordering on knowledge, that P != NP, but no one has been able to prove that it is the case. Falsifying this belief (that is to say, proving that P = NP) would be rather catastrophic for cryptography and very shocking to everyone in computer science, although perhaps it would also unlock amazing new possibilities in computer algorithms. According to a <a href=\"http:\/\/gregbaker.ca\/blog\/2010\/08\/07\/p-n-np\/\">recently distributed (leaked?) paper<\/a>, cryptographers can remain calm since P != NP. Even though this is what people believe, its proof would be a significant milestone for computer science.<\/p>\n<p>I promptly downloaded the paper, and as I suspected it was way out of my ability to comprehend without looking things up every few seconds at least, so if I really want to dive into the proof, I&#8217;d have to devote a lot more time to it, and if I really want to understand it I will have to devote years of study to complexity theory &#8212; assuming I&#8217;m smart enough to even get there. Nevertheless, if you want to take a look at the paper, but don&#8217;t want to download it from the login-required <a href=\"http:\/\/www.scribd.com\/doc\/35539144\/pnp12pt\">Scribd link<\/a> that everyone seems to be sharing, you can grab it <a href=\"In case you don't want to download it from scribd (requires login), grab the potentially super important paper about the P = NP problem here: http:\/\/arcanius.silverfir.net\/media\/p-vs-np-12pt.pdf\">here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Pretty big news breaking today about a possible breakthrough on the P vs NP problem, probably the most important unsolved problem in computer science today. Everyone suspects, to a degree bordering on knowledge, that P != NP, but no one has been able to prove that it is the case. Falsifying this belief (that is [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1888","post","type-post","status-publish","format-standard","hentry","category-everything"],"_links":{"self":[{"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/posts\/1888","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/comments?post=1888"}],"version-history":[{"count":4,"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/posts\/1888\/revisions"}],"predecessor-version":[{"id":1892,"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/posts\/1888\/revisions\/1892"}],"wp:attachment":[{"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/media?parent=1888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/categories?post=1888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/arcanius.silverfir.net\/blog\/wp-json\/wp\/v2\/tags?post=1888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}