# Classical NP-Complete Problems

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

- Review Sipser 7.5 “Additional NP-Complete Problems”.

**Reading Problem (Reductions)**

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

- Prove that vertex cover (\(\mathsf{COVER}\)) is NP-complete.
- 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.