Sipser 8.4-8.6

Read Sipser §8.4, §8.5, and §8.6

  1. 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.
  2. Explain why the book needs to give definition 8.20.
  3. Explain why we use log space reducibility (instead of polynomial space) to prove that languages are NL-hard.
  4. Summarize the logical steps behind the proof of Theorem 8.27.
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.