Sipser 9.1-9.2

Read Sipser §9.1 and §9.2

  1. Theorem 9.3 uses big-O and little-o notation. Review these definitions (page 276, section 7.1), and explain them in English words.
  2. Explain in your own words why Theorem 9.15 is equivalent to proving that the given language is intractable.
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.