Sipser 7.5

Read Sipser § 7.5

  1. Give a summary: How do we prove a problem is NP-complete?
  2. In the construction of the VERTEX-COVER instance in Theorem 7.44, the size of the vertex cover is set to be k = m + 2l, where m is the number of variables and l is the number of clauses in φ. How does this formula for k relate to the choice of vertices in the cover for the group? In other words, explain where m and 2l come from, and explain why these are the correct values.
  3. Explain what is happening in Figure 7.57.
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.