{"id":75,"date":"2008-07-03T19:55:13","date_gmt":"2008-07-04T00:55:13","guid":{"rendered":"http:\/\/vgable.com\/blog\/2008\/07\/03\/np-complete-is-often-easy\/"},"modified":"2008-07-03T19:55:14","modified_gmt":"2008-07-04T00:55:14","slug":"np-complete-is-often-easy","status":"publish","type":"post","link":"https:\/\/vgable.com\/blog\/2008\/07\/03\/np-complete-is-often-easy\/","title":{"rendered":"NP-Complete is Often Easy"},"content":{"rendered":"<blockquote><p> There are a lot of problems that are, in theory, incredibly difficult &#8211; but because the difficult cases are very rare and rather contrived, they&#8217;re actually very easy to solve. Two examples of this that I find particularly interesting are both NP complete. Type checking in Haskell is one of them: in fact, the general type inference in Haskell is worse that NP complete: the type validation is NP-complete; type inference is NP-hard. But on real code, it&#8217;s effectively approximately linear. The other one is a logic problem called 3-SAT. I once attended a great talk by a guy named Daniel Jackson, talking about a formal specification language he&#8217;d designed called Alloy. Alloy reduces its specification checking to 3-SAT. Dan explained this saying: &#8220;The bad news is, analyzing Alloy specifications is 3-SAT, so it&#8217;s exponential and NP-complete. But the good news is that analyzing Alloy specifications is 3-SAT, so we can solve it really quickly<\/p><\/blockquote>\n<p>&#8212;<a href=\"http:\/\/scienceblogs.com\/goodmath\/2008\/05\/linear_programming.php\">Mark Chu-Carroll (aka MarkCC<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>There are a lot of problems that are, in theory, incredibly difficult &#8211; but because the difficult cases are very rare and rather contrived, they&#8217;re actually very easy to solve. Two examples of this that I find particularly interesting are both NP complete. Type checking in Haskell is one of them: in fact, the general [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,4,24],"tags":[72,69,70,71],"class_list":["post-75","post","type-post","status-publish","format-standard","hentry","category-design","category-programming","category-quotes","tag-complexity","tag-haskell","tag-np-complete","tag-np-hard"],"_links":{"self":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/75","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/comments?post=75"}],"version-history":[{"count":0,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/75\/revisions"}],"wp:attachment":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/media?parent=75"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/categories?post=75"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/tags?post=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}