{"id":254,"date":"2024-08-02T18:19:56","date_gmt":"2024-08-02T18:19:56","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=254"},"modified":"2024-08-05T13:50:53","modified_gmt":"2024-08-05T13:50:53","slug":"sipser-8-3","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-8-3\/","title":{"rendered":"Sipser 8.3"},"content":{"rendered":"<p>Read Sipser &sect;8.3<\/p>\n<ol>\n<li>Sipser gives the definition of a \u201csentence\u201d to be a fully quantified Boolean formula. Write out a sentence (in the English language) that represents the Boolean formula that appears in the paragraph before this definition.\n<li> Recall the Cook-Levine theorem from chapter 7, and the role it played in proving languages were NP-complete. How can we use Theorem 8.9 in the future to prove that languages are PSPACE-complete?\n<li> Give an outline of the reduction that the textbook uses to show that GG is PSPACE-complete.\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect;8.3 Sipser gives the definition of a \u201csentence\u201d to be a fully quantified Boolean formula. Write out a sentence (in the English language) that represents the Boolean formula that appears in the paragraph before this definition. Recall the Cook-Levine theorem from chapter 7, and the role it played in proving languages were NP-complete. &#8230; <a title=\"Sipser 8.3\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-8-3\/\" aria-label=\"Read more about Sipser 8.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-254","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/254","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=254"}],"version-history":[{"count":1,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/254\/revisions"}],"predecessor-version":[{"id":255,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/254\/revisions\/255"}],"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=254"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}