{"id":6175,"date":"2012-03-22T22:38:41","date_gmt":"2012-03-23T05:38:41","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=6175"},"modified":"2012-03-22T22:38:41","modified_gmt":"2012-03-23T05:38:41","slug":"hardness-of-np","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2012\/03\/22\/hardness-of-np\/","title":{"rendered":"Hardness of NP"},"content":{"rendered":"<p>In computer science, NP-hard problems are widely believed to be intractable, not because they have been proved so, but on the empirical evidence of no one having found a fast algorithm for any of them in over half a century of trying.\u00a0 But the concepts of\u00a0 NP-hardness and NP-completeness are themselves hard for newcomers to understand. \u00a0 The current American Physical Society piece <a title=\"the Unbearable Hardness of Physics\" href=\"http:\/\/physics.aps.org\/synopsis-for\/10.1103\/PhysRevLett.108.120503\">Unbearable Hardness of Physics<\/a> makes a common mistake when it takes <strong>NP<\/strong>-hard problems to mean problems <strong>N<\/strong>ot solvable in time <strong>P<\/strong>olynomial in the size of their input, rather than those to which <em>all<\/em> problems solvable in <strong>N<\/strong>ondeterministic <strong>P<\/strong>olynomial time are efficiently reducible.\u00a0 Come to think of it, the letters <strong>N<\/strong> and <strong>P<\/strong>\u00a0 also breed confusion in other fields, including our own, where\u00a0 <strong>NPT<\/strong> is often taken to stand for <strong>N<\/strong>egative <strong>P<\/strong>artial <strong>T<\/strong>ranspose, when it would be more correct to say <strong>N<\/strong>onpositive <strong>P<\/strong>artial <strong>T<\/strong>ranspose, admittedly a tiny imprecision compared to the confusion surrounding what <strong>NP <\/strong>means.<br \/>\n&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In computer science, NP-hard problems are widely believed to be intractable, not because they have been proved so, but on the empirical evidence of no one having found a fast algorithm for any of them in over half a century of trying.\u00a0 But the concepts of\u00a0 NP-hardness and NP-completeness are themselves hard for newcomers to &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/dabacon.org\/pontiff\/2012\/03\/22\/hardness-of-np\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Hardness of NP&#8221;<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[32,48,90],"tags":[],"class_list":["post-6175","post","type-post","status-publish","format-standard","hentry","category-general","category-nitpickers-paradiso","category-words"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6175","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=6175"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6175\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=6175"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=6175"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=6175"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}