Assignment VII

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).