{"id":15627,"date":"2015-09-30T13:43:21","date_gmt":"2015-09-30T18:43:21","guid":{"rendered":"http:\/\/bucktownbell.com\/?p=15627"},"modified":"2015-09-30T13:43:21","modified_gmt":"2015-09-30T18:43:21","slug":"edit-distance-reveals-hard-computational-problems","status":"publish","type":"post","link":"http:\/\/bucktownbell.com\/?p=15627","title":{"rendered":"Edit Distance Reveals Hard Computational Problems"},"content":{"rendered":"<blockquote><p>As far as computer scientists know, the only general-purpose method to find the correct answer to a SAT problem is to try all possible settings of the variables one by one. The amount of time that this exhaustive or \u201cbrute-force\u201d approach takes depends on how many variables there are in the formula. As the number of variables increases, the time it takes to search through all the possibilities increases exponentially. To complexity theorists and algorithm designers, this is bad. (Or, technically speaking, hard.)<\/p>\n<p>SETH takes this situation from bad to worse. It implies that finding a better general-purpose algorithm for SAT \u2014 even one that only improves on brute-force searching by a small amount \u2014 is impossible.<\/p><\/blockquote>\n<p>Source: <em><a href=\"https:\/\/www.quantamagazine.org\/20150929-edit-distance-computational-complexity\/\">Edit Distance Reveals Hard Computational Problems | Quanta Magazine<\/a><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>As far as computer scientists know, the only general-purpose method to find the correct answer to a SAT problem is to try all possible settings of the variables one by one. The amount of time that this exhaustive or \u201cbrute-force\u201d &hellip; <a href=\"http:\/\/bucktownbell.com\/?p=15627\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[737],"tags":[670,1060,180,726],"class_list":["post-15627","post","type-post","status-publish","format-standard","hentry","category-stem","tag-algorithms","tag-computer-science","tag-math","tag-system-test"],"_links":{"self":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts\/15627","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=15627"}],"version-history":[{"count":1,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts\/15627\/revisions"}],"predecessor-version":[{"id":15628,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts\/15627\/revisions\/15628"}],"wp:attachment":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=15627"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=15627"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=15627"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}