CSE 237 Spring 2006
Homework
11b
due 4/28/06
Submit these problems TOGETHER with Homework 11a as one homework.
Start each problem on a new sheet.
You can make use of any theorem that was presented/proved in class.
You are encouraged to discuss the homework problems in groups -- as long as you do the writing by yourself.
Problem 5. VP (polynomial verifiability)
(a) Show that MAX-CUT is in VP (defined in an Exercise in chapter 7).
(b) Show that ISO is in VP (defined in an Exercise in chapter 7). Note that isomorphism only looks at how nodes are connected; it ignores the labels of nodes and edges, if any.
Problem 6. Reductions to YES/NO problems
(a) The CLIQUE problem (defined in chapter 7) takes k, the size of the clique, as one of the arguments. This problem is NP-complete (it is in NP, and no polynomial-time solution is known).
Show that, if CLIQUE was in P (that is, if NP = P), then there exists a polynomial-time algorithm NEWCLIQUE that, given a graph (and nothing else), finds the largest clique in it (or one of them, if there is more). Note: NEWCLIQUE is not a YES/NO algorithm, since it returns the actual clique.
Hint: use CLIQUE as a boolean subroutine for NEWCLIQUE .
(b) The SAT problem (defined in chapter 7) takes a boolean formula f and decides whether f is satisfiable. This problem is NP-complete (it is in NP, and no polynomial-time solution is known).
Show that, if SAT was in P (that is, if NP = P), then there exists a polynomial-time algorithm FINDSAT that, given a boolean formula f, produces a satisfying assignment for it (if one exists). Note: FINDSAT is not a YES/NO algorithm, since it returns the actual assignment.
Hint: use SAT as a boolean subroutine for FINDSAT , with an approach analogous to that in (a).