CS代考 Ex.: – cscodehelp代写

Ex.:

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.