Sipser 7.1-7.2

Read Sipser § 7.1 and § 7.2

  1. True or False: The time complexity of a language A depends on the model of computation that is used.
  2. 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?
  3. What is the complexity class P? Answer in a sentence or two.
  4. How do we show that a language belongs to P? Answer in a sentence or two.
css.php
The views and opinions expressed on individual web pages are strictly those of their authors and are not official statements of Grinnell College. Copyright Statement.