[SOLVED] Cse 3500: problem set 6

Question 1. (10 points) Suppose someone gives you a polynomial time algorithm for deciding the
3-SAT problem (yes/no answer to whether there exists a satisfying assignment for the 3-CNF expression). Show how to use this algorithm to compute a satisfying assignment in polynomial time.
Question 2. (10 points) Exercise 22 from Chapter 8, page 517 of the textbook.
Question 3. (10 points) Exercise 5, Chapter 8, p. 506. (For the reduction, you should use one of
the problems we have already shown to be NP-complete in class.)
Question 4. (10 points) (10 points for answering (no right or wrong answers!))
(a) Which topics did you enjoy learning about the most and why?
(b) Name one or more topic(s) that you found easy to understand.
(c) Name one or more topic(s) that you found difficult to understand.