{"id":4113,"date":"2011-12-06T00:00:00","date_gmt":"2011-12-06T05:00:00","guid":{"rendered":"http:\/\/www.webliminal.com\/webliminalblog\/uncategorized\/links-for-december-5-2011"},"modified":"2012-03-25T15:58:54","modified_gmt":"2012-03-25T20:58:54","slug":"links-for-december-5-2011","status":"publish","type":"post","link":"http:\/\/www.webliminal.com\/webliminalblog\/uncategorized\/links-for-december-5-2011","title":{"rendered":"P vs NP links"},"content":{"rendered":"<p><a href=\"http:\/\/webliminal.com\/images\/sidepics\/sp75.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft\" style=\"margin-left: 22px; margin-right: 22px;\" src=\"http:\/\/webliminal.com\/images\/sidepics\/cwdata\/sp75.jpg\" alt=\"Wild Azalea, Shenandoah National Park, Va\" width=\"160\" height=\"120\" align=\"left\" \/><\/a>Links about P vs NP <\/p>\n<ul>\n<li><a href=\"http:\/\/blogs.discovermagazine.com\/80beats\/2010\/08\/10\/has-the-devilish-math-problem-p-vs-np-finally-been-solved\/\">Has the Devilish Math Problem \u00e2\u20ac\u0153P vs NP\u00e2\u20ac\u009d Finally Been Solved? | 80beats | Discover Magazine<\/a> &#8211; &#8220;P is not equal to NP. Seems simple enough. But if it\u00e2\u20ac\u2122s true, it could be the answer to a problem computer scientists have wrestled for decades.<br \/>\nVinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. &#8220;<\/li>\n<li><a href=\"http:\/\/cacm.acm.org\/magazines\/2009\/9\/38904-the-status-of-the-p-versus-np-problem\/fulltext\">The Status of the P Versus NP Problem | September 2009 | Communications of the ACM<\/a> &#8211; &#8220;The theory of NP-completeness helps us understand these limitations and the P versus NP problem begins to loom large not just as an interesting theoretical question in computer science, but as a basic principle that permeates all the sciences.&#8221;<\/li>\n<li><a href=\"http:\/\/www.nada.kth.se\/~viggo\/wwwcompendium\/\">A compendium of NP optimization problems<\/a> &#8211; &#8220;This is a continuously updated catalog of approximability results for NP optimization problems. The compendium is also a part of the book Complexity and Approximation. The compendium has not been updated for a while, so there might exist recent results that are not mentioned in the compendium. If you happen to notice such a missing result, please report it to us using the web forms.&#8221;<\/li>\n<li><a href=\"http:\/\/www.physorg.com\/news98988548.html\">CMU professor honored for computational complexity breakthrough<\/a> &#8211; &#8221; In a paper presented at the Symposium on Theory of Computing in 1994 and published in 1997 in the Journal of Computer and System Sciences, they showed that a wide class of proof techniques they call &#8220;natural proofs&#8221; can&#8217;t solve the P vs. NP question. What&#8217;s more, they found that those previous results turned out to have an almost contradictory double life, providing methods for breaking a wide class of cryptosystems.&#8221;<\/li>\n<\/ul>\n<!-- AddThis Advanced Settings generic via filter on the_content --><!-- AddThis Share Buttons generic via filter on the_content -->","protected":false},"excerpt":{"rendered":"<p>Links about P vs NP Has the Devilish Math Problem \u00e2\u20ac\u0153P vs NP\u00e2\u20ac\u009d Finally Been Solved? | 80beats | Discover Magazine &#8211; &#8220;P is not equal to NP. Seems simple enough. But if it\u00e2\u20ac\u2122s true, it could be the answer to a problem computer scientists have wrestled for decades. Vinay Deolalikar, who is with Hewlett-Packard [&hellip;]<!-- AddThis Advanced Settings generic via filter on get_the_excerpt --><!-- AddThis Share Buttons generic via filter on get_the_excerpt --><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[951,1446,949,955,953,97,944,945,946,1447,141,950,947,957,204,954,956,952,249,943,251,1452,948],"class_list":["post-4113","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-algorithms","tag-books","tag-bookslist","tag-complexity","tag-computerscience","tag-cs","tag-eating-out","tag-ethical","tag-ethics","tag-food","tag-guide","tag-influential","tag-labor","tag-math","tag-np","tag-nphard","tag-optimization","tag-pnp","tag-research","tag-restaraunt","tag-restaurant","tag-travel","tag-workers-rights"],"_links":{"self":[{"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/posts\/4113","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/comments?post=4113"}],"version-history":[{"count":4,"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/posts\/4113\/revisions"}],"predecessor-version":[{"id":4238,"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/posts\/4113\/revisions\/4238"}],"wp:attachment":[{"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/media?parent=4113"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/categories?post=4113"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.webliminal.com\/webliminalblog\/wp-json\/wp\/v2\/tags?post=4113"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}