{"id":252,"date":"2024-08-02T18:18:37","date_gmt":"2024-08-02T18:18:37","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=252"},"modified":"2024-10-28T00:38:20","modified_gmt":"2024-10-28T00:38:20","slug":"sipser-8-1-8-2","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-8-1-8-2\/","title":{"rendered":"Sipser 8.1-8.2"},"content":{"rendered":"<p>Read Sipser \u00a78.1 and \u00a78.2<\/p>\n<ol>\n<li>The reading proves that while SAT is NP-complete, it only takes a linear amount of space, i.e. it is in PSPACE. Adapt this proof technique to show that CLIQUE is also in PSPACE.<\/li>\n<li>In the machine described on page 333, the machine seemingly runs in exponential (ie greater than polynomial) time. Describe why this is not a problem for this analysis.<\/li>\n<li>Savitch\u2019s theorem tells us something about the difference in space complexity between deterministic and nondeterministic Turing Machines. What could we say about time complexity between deterministic and nondeterministic Turing Machines?<\/li>\n<li>In the proof of Savitch\u2019s theorem, summarize why the constructed machine M correctly simulates N in a deterministic way.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser \u00a78.1 and \u00a78.2 The reading proves that while SAT is NP-complete, it only takes a linear amount of space, i.e. it is in PSPACE. Adapt this proof technique to show that CLIQUE is also in PSPACE. In the machine described on page 333, the machine seemingly runs in exponential (ie greater than polynomial) &#8230; <a title=\"Sipser 8.1-8.2\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-8-1-8-2\/\" aria-label=\"Read more about Sipser 8.1-8.2\">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-252","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/252","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=252"}],"version-history":[{"count":2,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/252\/revisions"}],"predecessor-version":[{"id":367,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/252\/revisions\/367"}],"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=252"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}