{"id":250,"date":"2024-08-02T18:16:45","date_gmt":"2024-08-02T18:16:45","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=250"},"modified":"2024-08-02T19:36:41","modified_gmt":"2024-08-02T19:36:41","slug":"sipser-7-5","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-7-5\/","title":{"rendered":"Sipser 7.5"},"content":{"rendered":"<p><script id=\"MathJax-script\" async src=\"https:\/\/cdn.jsdelivr.net\/npm\/mathjax@3\/es5\/tex-mml-chtml.js\"><\/script><\/p>\n<p>Read Sipser &sect; 7.5<\/p>\n<ol>\n<li> Give a summary: How do we prove a problem is NP-complete?\n<li> In the construction of the VERTEX-COVER instance in Theorem 7.44, the size of the vertex cover is set to be k = m + 2l, where m is the number of variables and l is the number of clauses in &phi;. How does this formula for k relate to the choice of vertices in the cover for the group? In other words, explain where m and 2l come from, and explain why these are the correct values.\n<li> Explain what is happening in Figure 7.57.\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect; 7.5 Give a summary: How do we prove a problem is NP-complete? In the construction of the VERTEX-COVER instance in Theorem 7.44, the size of the vertex cover is set to be k = m + 2l, where m is the number of variables and l is the number of clauses in &#8230; <a title=\"Sipser 7.5\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-7-5\/\" aria-label=\"Read more about Sipser 7.5\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":29,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-250","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/comments?post=250"}],"version-history":[{"count":3,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/250\/revisions"}],"predecessor-version":[{"id":285,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/250\/revisions\/285"}],"up":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/media?parent=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}