{"id":256,"date":"2024-08-02T18:21:52","date_gmt":"2024-08-02T18:21:52","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=256"},"modified":"2024-08-02T18:22:01","modified_gmt":"2024-08-02T18:22:01","slug":"sipser-8-4-8-6","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-8-4-8-6\/","title":{"rendered":"Sipser 8.4-8.6"},"content":{"rendered":"<p>Read Sipser &sect;8.4, &sect;8.5, and &sect;8.6<\/p>\n<ol>\n<li> The book gives CD-ROMs as an example in this reading, however many of our modern day computers do not support CD-ROMs. Give a modern example that fits the same idea of a read-only input tape.\n<li> Explain why the book needs to give definition 8.20.\n<li> Explain why we use log space reducibility (instead of polynomial space) to prove that languages are NL-hard.\n<li> Summarize the logical steps behind the proof of Theorem 8.27.\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect;8.4, &sect;8.5, and &sect;8.6 The book gives CD-ROMs as an example in this reading, however many of our modern day computers do not support CD-ROMs. Give a modern example that fits the same idea of a read-only input tape. Explain why the book needs to give definition 8.20. Explain why we use log &#8230; <a title=\"Sipser 8.4-8.6\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-8-4-8-6\/\" aria-label=\"Read more about Sipser 8.4-8.6\">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-256","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/256","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=256"}],"version-history":[{"count":1,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/256\/revisions"}],"predecessor-version":[{"id":257,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/256\/revisions\/257"}],"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=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}