Sipser 8.1-8.2

Read Sipser §8.1 and §8.2

  1. The reading proves that while SAT is NP-complete, it only takes a linear amount of space, i.e. it is in PSPACE. Adapt this proof technique to show that CLIQUE is also in PSPACE.
  2. In the machine described on page 333, the machine seemingly runs in exponential (ie greater than polynomial) time. Describe why this is not a problem for this analysis.
  3. Savitch’s theorem tells us something about the difference in space complexity between deterministic and nondeterministic Turing Machines. What could we say about time complexity between deterministic and nondeterministic Turing Machines?
  4. In the proof of Savitch’s theorem, summarize why the constructed machine M correctly simulates N in a deterministic way.
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.