1. Given the SAT problem from lecture for a Boolean expression in Conjunctive Normal Form with any number of clauses and any number of literals in each clause. For example,
(X1 X3) (X1 X2 X4 X5) …
Prove that SAT is polynomial time reducible to the 3-SAT problem (in which each clause contains at most 3 literals.)
2. The Set Packing problem is as follows. We are given m sets S1, S2, … Sm and an integer k. Our goal is to select k of the m sets such that no selected pair have any elements in common. Prove that this problem is NP-complete.
3. The Steiner Tree problem is as follows. Given an undirected graph G=(V,E) with nonnegative edge costs and whose vertices are partitioned into two sets, R and S, find a tree T ⊆ G such that for every v in R, v is in T with total cost at most C. That is, the tree that contains every vertex in R (and possibly some in S) with a total edge cost of at most C.
Prove that this problem is NP-complete.
