This is not a homework, but just a collection of problems from Lectures 30 of
Jeff
Erickson's notes. The problems are on concepts surrounding P, NP, and NP-completeness. For the last two problems, prove that they are NP-complete, and not just that they are NP-hard.
- Exercise 3 of Lecture 30.
- Exercise 13 of Lecture 30.
- Exercise 23 of Lecture 30.
- Exericse 24 of Lecture 30.
Take a look at these problems. We will solve some of them on the last day of classes.