CSC 341 (Fall 2021)

Reading: P vs NP

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.


Reading Problem (Reductions Concluded)

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