Question $4$: NP$-$Hardness $-$ Set Packing Problem $(15$ pts$).$

The Set Packing Problem is stated as follows: Given a set U of n elements, a collection S $1,$ S $2,...,$ S m of

subsets of U $,$ and a number k$,$ does there exist a collection of at least k of these subsets with the property that

no two of them intersect?

Show that Set Packing is NP$-$hard. Hint: which well$-$known NP$-$hard problem can be reduced to this

problem?