{"id":890,"date":"2016-11-21T15:36:07","date_gmt":"2016-11-21T23:36:07","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=890"},"modified":"2016-11-21T15:36:07","modified_gmt":"2016-11-21T23:36:07","slug":"lecture-20161121","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc320\/2016\/11\/21\/lecture-20161121\/","title":{"rendered":"Lecture 2016\/11\/21"},"content":{"rendered":"<p>Today we&#8217;ll make a reduction to prove the Steiner Tree Problem is NP-hard (and therefore NP-complete, since it&#8217;s in NP). We won&#8217;t prove the reduction correct quite yet, however.<\/p>\n<p>Note: this is a doozy of a reduction. So, it&#8217;s good practice for us, but\u00a0<strong>much<\/strong> harder than, e.g., the SAT\/ELEC problem on the assignment!<\/p>\n<ul>\n<li>Here is the new handout on <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/files\/2016\/11\/2016-11-16-np-compleness-pt2.pdf\">NP-hardness of SP<\/a>.<\/li>\n<li>For Wednesday, please read section 8.7 of the textbook (about the famous 3-coloring problem in graphs!). This is also a good time to go back and re-skim 8.10. You&#8217;ve seen a lot of those problems now!<\/li>\n<li>No quiz for Wednesday.<\/li>\n<li>Keep trucking on the assignment due Thursday!<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Today we&#8217;ll make a reduction to prove the Steiner Tree Problem is NP-hard (and therefore NP-complete, since it&#8217;s in NP). We won&#8217;t prove the reduction correct quite yet, however. Note: this is a doozy of a reduction. So, it&#8217;s good practice for us, but\u00a0much harder than, e.g., the SAT\/ELEC problem on the assignment! Here is &hellip; <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/2016\/11\/21\/lecture-20161121\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Lecture 2016\/11\/21&#8221;<\/span><\/a><\/p>\n","protected":false},"author":7560,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[318531,99],"tags":[],"class_list":["post-890","post","type-post","status-publish","format-standard","hentry","category-handouts","category-readings"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/890","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/users\/7560"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/comments?post=890"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/890\/revisions"}],"predecessor-version":[{"id":892,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/890\/revisions\/892"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/media?parent=890"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/categories?post=890"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/tags?post=890"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}