{"id":232,"date":"2024-08-02T18:05:28","date_gmt":"2024-08-02T18:05:28","guid":{"rendered":"http:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/?page_id=232"},"modified":"2024-08-02T18:05:40","modified_gmt":"2024-08-02T18:05:40","slug":"232-2","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/schedule\/232-2\/","title":{"rendered":"Sipser 7.1-7.2"},"content":{"rendered":"<p>Read Sipser &sect; 7.1 and &sect; 7.2<\/p>\n<ol>\n<li> True or False: The time complexity of a language A depends on the model of computation that is used.\n<li> In theorem 7.11, we show that a DTM can simulate a NTM with runtime t(n) in 2^{O(t(n))} time. How does the proof of the theorem bound the total number of leaves in the tree when a Turing machine can potentially go into infinite loops?\n<li> What is the complexity class P? Answer in a sentence or two.\n<li> How do we show that a language belongs to P? Answer in a sentence or two.\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect; 7.1 and &sect; 7.2 True or False: The time complexity of a language A depends on the model of computation that is used. In theorem 7.11, we show that a DTM can simulate a NTM with runtime t(n) in 2^{O(t(n))} time. How does the proof of the theorem bound the total number &#8230; <a title=\"Sipser 7.1-7.2\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/schedule\/232-2\/\" aria-label=\"Read more about Sipser 7.1-7.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-232","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/232","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/comments?post=232"}],"version-history":[{"count":2,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/232\/revisions"}],"predecessor-version":[{"id":234,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/232\/revisions\/234"}],"up":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/media?parent=232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}