Due date Dec. 10
1. From text: 7.16 (find short paths is easy, long paths are hard).
2. From text: 7.19 (two solutions to 3SAT is as hard as one).
3. From text: 7.22 (restricted solutions to 3SAT are as hard as 3SAT).
4. From text: 7.26 (doesn't look like a graph, and doesn't look like a
boolean formula, but can encode one of those).
5. From text: 7.37 (sketch an algorithm to solve 2SAT, and show that it
it is polynomial in the number of variables and the number of clauses).