CSC 341 (Fall 2021)

Reading: Classical NP-Complete Problems

Classical NP-Complete Problems

We’ll continue our discussion of NP-completeness by studying mapping reductions of classic NP-complete problems in detail.

Reading Problem (Reductions)

Complete and submit one of the two NP-complete problems introduced in last class’s daily:

  1. Prove that vertex cover (\(\mathsf{COVER}\)) is NP-complete.
  2. Sipser 7.28. Prove that the card puzzle problem (\(\mathsf{PUZZLE}\)) is NP-complete.

Remember to prove both parts of the definition of NP-completeness: membership in NP and NP-hardness. Make sure that you also argue both directions of the reduction’s correctness condition.