{"id":280,"date":"2009-08-09T15:58:55","date_gmt":"2009-08-09T14:58:55","guid":{"rendered":"http:\/\/www.nobugs.org\/blog\/?p=280"},"modified":"2009-08-09T15:58:55","modified_gmt":"2009-08-09T14:58:55","slug":"reducing-vs-decomposing","status":"publish","type":"post","link":"https:\/\/www.nobugs.org\/blog\/archives\/2009\/08\/09\/reducing-vs-decomposing\/","title":{"rendered":"Reducing vs decomposing"},"content":{"rendered":"<p>A small distinction which I remembered about today &#8211; it was in the SICP videos I watched a while ago.  If a problem A can be <i>reduced<\/i> to a simpler problem B, then once you&#8217;ve made that step you can forget about problem A entirely, safe in the knowledge that the answer to B will do just as well.  In contrast, a problem which can be <i>decomposed<\/i> into sub-problems might yet require the sub-answers to be combined in some way to get the final results.  Therefore, you need to do more bookkeeping in order to track the results of the subproblems.<\/p>\n<p>To a programmer, this is just the difference between a tail-call and a non-tail call.  But the insight pertains to how some programmer use the phrases &#8220;reduces to ..&#8221; and &#8220;decomposes into ..&#8221; to mean two subtly different things.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A small distinction which I remembered about today &#8211; it was in the SICP videos I watched a while ago. If a problem A can be reduced to a simpler problem B, then once you&#8217;ve made that step you can forget about problem A entirely, safe in the knowledge that the answer to B will [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-280","post","type-post","status-publish","format-standard","hentry","category-general"],"_links":{"self":[{"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/posts\/280","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/comments?post=280"}],"version-history":[{"count":3,"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/posts\/280\/revisions"}],"predecessor-version":[{"id":283,"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/posts\/280\/revisions\/283"}],"wp:attachment":[{"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/media?parent=280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/categories?post=280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.nobugs.org\/blog\/wp-json\/wp\/v2\/tags?post=280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}