{"id":44,"date":"2009-09-12T19:03:00","date_gmt":"2009-09-12T19:03:00","guid":{"rendered":"http:\/\/graham-kendall.com\/blog\/?p=44"},"modified":"2020-09-22T02:01:59","modified_gmt":"2020-09-22T02:01:59","slug":"p-vs-np","status":"publish","type":"post","link":"https:\/\/graham-kendall.com\/blog\/p-vs-np\/","title":{"rendered":"P vs NP"},"content":{"rendered":"<p>I have just read an excellent article in the latest issue of Communications of the ACM.<\/p>\n<p>Fortnow L. (2009) The Status of the P versus NP Problem Communications of the ACM, 52(9):78-86 (doi:<a href=\"http:\/\/dx.doi.org\/10.1145\/1562164.1562186\">10.1145\/1562164.1562186<\/a>)<\/p>\n<p>The article not only describes what the P=NP problem is (and it is one of the best non-technical descriptions I have seen) but also provides some of the research directions that might lead to a proof that P=NP (or, more likely (in my view &#8211; and many others), that P?NP).<\/p>\n<p>If you are any sort of computer scientist, then I would urge you to take a look at this article.<\/p>\n<p>You can stay up to date with this area on the author&#8217;s blog (<a href=\"http:\/\/blog.computationalcomplexity.org\/\">http:\/\/blog.computationalcomplexity.org<\/a>)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I have just read an excellent article in the latest issue of Communications of the ACM. Fortnow L. (2009) The Status of the P versus NP Problem Communications of the ACM, 52(9):78-86 (doi:10.1145\/1562164.1562186) The article not only describes what the P=NP problem is (and it is one of the best non-technical descriptions I have seen) [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[177,68],"tags":[69],"class_list":["post-44","post","type-post","status-publish","format-standard","hentry","category-archive","category-theory","tag-pnp"],"_links":{"self":[{"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/posts\/44","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/comments?post=44"}],"version-history":[{"count":1,"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/posts\/44\/revisions"}],"predecessor-version":[{"id":1691,"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/posts\/44\/revisions\/1691"}],"wp:attachment":[{"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/media?parent=44"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/categories?post=44"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/graham-kendall.com\/blog\/wp-json\/wp\/v2\/tags?post=44"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}