Sipser 8.3

Read Sipser §8.3

  1. Sipser gives the definition of a “sentence” to be a fully quantified Boolean formula. Write out a sentence (in the English language) that represents the Boolean formula that appears in the paragraph before this definition.
  2. Recall the Cook-Levine theorem from chapter 7, and the role it played in proving languages were NP-complete. How can we use Theorem 8.9 in the future to prove that languages are PSPACE-complete?
  3. Give an outline of the reduction that the textbook uses to show that GG is PSPACE-complete.
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.