Problem 1 (5 points): In Ch8.ppt review the reduction of CIRCUIT-SAT to 3-SAT. (It is the slide titled “3-SAT is NP-Complete”, around slide 17.) Apply this reduction to the CIRCUIT-SAT instance on slide 14, and show the resulting 3-SAT problem instance. Is the instance an element of 3-SAT? (I.e., Is it satisfiable?)
Problem 2 (5 points): In Ch8.ppt review the reduction of 3-SAT to INDEPENDENT-SAT.
(“Independent Set is NP-Complete”, around slide 19.) Apply this reduction to the formula:
(¬x ¬y z) (x y ¬z) (¬x z) (x ¬z)
Show the resulting INDEPENDENT-SET instance. (Be sure to specify both the graph and the natural number g.) Is the instance an element of INDEPENDENT-SET? (I.e., Does it have an independent set of the size specified by the transformation?)
Problem 3 (5 points): Review the reduction of INDEPENDENT-SET to CLIQUE from the Ch8 notes. (“CLIQUE is NP-Complete”, around slide 21.) Apply the reduction to the instance (G,3) where G is this graph:
B
A D
C
Show the resulting CLIQUE problem instance. (Be sure to specify both the graph and the natural number g.) Is the instance an element of CLIQUE? (I.e., Does it have a clique of the size specified by the transformation?)
Problem 4 (10 points): Exercise 8.4(a-c) in the textbook.
Hints:
Part (a) Hint: Review Ch8.ppt, slides 5-8. Give a polynomial time algorithm that works as a certifier for CLIQUE-3. You do not need to specify a lot of detail. One or two clearly expressed sentences may suffice. You should specify: (1) what form a certificate takes (e.g. “A certificate is a set of _______ from the graph.”) and (2) explain what the certifier algorithm does with the
certificate (e.g. “The certifier returns true if ___________ and otherwise returns false.”).
Part (b) Hint: Review the “recipe” on Slide 16. How is the given argument failing to follow the recipe?
Part (c) The part that is incorrect is the sentence that starts “Now, a subset C ...”. Give a counterexample showing that this sentence is false.
You are not asked to solve Part (d), but here is a solution for your edification:
Note that the largest clique in a CLIQUE-3 problem can have size at most 4. So if g 4 the answer is ‘false’: the instance is not in CLIQUE-3. If g ≤ 4 then the following O(|V|4) algorithm will determine whether the instance is in CLIQUE-3:
for u1 in V:
for u2 in V:
for u3 in V:
for u4 in V:
let S = {u1,u2,u3,u4}
if |S| = g and each pair of elements in S has an edge between them:
return true
return false
