Prove that 3-Sat(15/16) is NP-complete.
Hint: If x, y, and z are literals, there are eight possible clauses containing them: (x ∨ y ∨ z), (!x ∨ y ∨ z), (x∨!y ∨ z), (x ∨ y∨!z), (!x∨!y ∨ z), (!x ∨ y∨!z), (x∨!y∨!z), (!x∨!y∨!z)
Problem 3 (25 pts)
Consider a modified SAT problem, SAT’ in which given a CNF formula having m clauses and n variables x1,x2,...,xn, the output is YES if there is an assignment to the variables such that exactly m − 2 clauses are satisfied, and NO otherwise. Prove that SAT’ is NP-Complete.
Problem 4 (25 pts)
Show that Vertex Cover is still NP-complete even when all vertices in the graph are restricted to have even degree.
Practice Problems
Problem 5 (25 pts)
(Kleinberg and Tardos, Chapter 8, Exercise 5)
Consider a set A = {a1,...,an} and a collection B1,B2,...,Bm of subsets of A (i.e., Bi ⊆ A for each i).
We say that a set H ⊆ A is a hitting set for the collection B1,B2,...,Bm if H contains at least one element from each Bi—that is, if H ∩ Bi is not empty for each i (so H “hits” all the sets Bi).
We now define the Hitting Set Problem as follows. We are given a set A = {a1,...,an}, a collection B1,B2,...,Bm of subsets of A, and a number k. We are asked: Is there a hitting set H ⊆ A for B1,B2,...,Bm so that the size of H is at most k?
Prove that Hitting Set is NP-complete.
