Discussion 10
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.