{"id":235,"date":"2024-08-02T18:08:00","date_gmt":"2024-08-02T18:08:00","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=235"},"modified":"2024-08-02T18:13:33","modified_gmt":"2024-08-02T18:13:33","slug":"sipser-7-3","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-7-3\/","title":{"rendered":"Sipser 7.3"},"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.3 and part of &#038;sect 7.4: through page 304. <\/p>\n<ol>\n<li> How do we define the class NP in terms of a \u201ccertificate\u201d? How does the \u201ccertificate\u201d relate to the \u201cnon-determinism\u201d part of NP?\n<li> How do I show that a language is NP-complete?\n<li> Suppose that \\[ A \\leq_p B .\\] Describe what our textbook means by this inequality. From which of the two languages are we inferring information?\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect; 7.3 and part of &#038;sect 7.4: through page 304. How do we define the class NP in terms of a \u201ccertificate\u201d? How does the \u201ccertificate\u201d relate to the \u201cnon-determinism\u201d part of NP? How do I show that a language is NP-complete? Suppose that \\[ A \\leq_p B .\\] Describe what our textbook &#8230; <a title=\"Sipser 7.3\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-7-3\/\" aria-label=\"Read more about Sipser 7.3\">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-235","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/235","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=235"}],"version-history":[{"count":8,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/235\/revisions"}],"predecessor-version":[{"id":248,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/235\/revisions\/248"}],"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=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}