# P vs NP

We’ll wrap-up our discussion of NP-Completeness by reviewing the NP-completeness proof technique. With the time remaining we’ll contextualize the Million Dollar P vs NP Problem before we move onto space complexity! If you’re interested in learning more about the current state of the P vs NP problem, read this excellent overview by theory of computation researcher Scott Aaronson.

- Scott Aaronson. \(\mathsf{P} \stackrel{?}{=} \mathsf{NP}\). https://www.scottaaronson.com/papers/pnp.pdf

**Reading Problem (Reductions Concluded)**

Complete and submit the *other* of the two NP-complete problems introduced in Monday’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.