Sipser 7.3

Read Sipser § 7.3 and part of &sect 7.4: through page 304.

  1. How do we define the class NP in terms of a “certificate”? How does the “certificate” relate to the “non-determinism” part of NP?
  2. How do I show that a language is NP-complete?
  3. Suppose that \[ A \leq_p B .\] Describe what our textbook means by this inequality. From which of the two languages are we inferring information?
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.