Due date Monday Dec.1.
1. From text: problems 7.1 and 7.2
2. From text: 7.19: show that double satisfiability is NP-complete.
Recall that this requires that you prove: a) that the problem is in NP, and
b) that a known NP-complete problem can be reduced to it.
3. Complete the proof of 7.26, which we discussed in class, that is to say
show how to make an instance of this game that solves a given 3SAT problem.
4. How many satisfying truth assignments do the following boolean expressions
a) x and (y or not x) and (z or not y)
b) (x or y) and ( not (x or z) or (not x and not y))
5. Recall that a Hamiltonian circuit in a graph is a path that returns to its
starting node after visiting each node once.
a) A graph that is a square has a Hamiltonian circuit (easy).
b) A a graph that is cube also has a Hamiltonian circuit (a little harder).
c) Show that the following graph has no Hamitonian circuit:
| | |
| | |
Hint: think about any path that goes through the center node.
6. (Optional): the firehouse problem (to be known in the future as the
Bloomberg problem): given a graph G, a maximum distance d, and a number
of firehouses f, choose f nodes in G so that no node in G is at a distance
(number of edges to be traversed) greater than d from some firehouse.
Show that the problem is NP-complete.