{"id":4228,"date":"2014-03-30T09:24:46","date_gmt":"2014-03-30T09:24:46","guid":{"rendered":"https:\/\/unknownerror.org\/index.php\/2014\/03\/30\/np-complete-but-not-hard-closed-collection-of-common-programming-errors\/"},"modified":"2014-03-30T09:24:46","modified_gmt":"2014-03-30T09:24:46","slug":"np-complete-but-not-hard-closed-collection-of-common-programming-errors","status":"publish","type":"post","link":"https:\/\/unknownerror.org\/index.php\/2014\/03\/30\/np-complete-but-not-hard-closed-collection-of-common-programming-errors\/","title":{"rendered":"np-complete but not &ldquo;hard&rdquo; [closed]-Collection of common programming errors"},"content":{"rendered":"<p>Is there some language that is NP-complete but for which we know some &#8220;quick&#8221; algorithm? I don&#8217;t mean like the ones for knapsack where we can do well on average, I mean that even in the worst case the runtime is something like 2^n^epsilon, where the result holds for any epsilon&gt;0 and so we can allow it to get arbitrarily close to 0.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Is there some language that is NP-complete but for which we know some &#8220;quick&#8221; algorithm? I don&#8217;t mean like the ones for knapsack where we can do well on average, I mean that even in the worst case the runtime is something like 2^n^epsilon, where the result holds for any epsilon&gt;0 and so we can [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-4228","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/posts\/4228","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/comments?post=4228"}],"version-history":[{"count":0,"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/posts\/4228\/revisions"}],"wp:attachment":[{"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/media?parent=4228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/categories?post=4228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/unknownerror.org\/index.php\/wp-json\/wp\/v2\/tags?post=4228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}