Prove that the problems below are NP-complete. You can assume that the following problems are NPcomplete: 3SAT, HamPath, Partition, Clique, and !=SAT. Make sure you show that the problems are in NP, then give respective reductions and give an if and only if argument for reduction correctness, as well as say why your reduction runs in polynomial time.

a. k-Clique HamPath: kCHP = { |G is an undirected graph and k ? N, and G contains both a clique of size k and a Hamiltonian path}.

b. Representatives: Rep = { |S1, . . . , Sm are subsets of some set U with |U| = n, k ? N, and there is a set S ? U, |S| ? k, which contains at least one element from each of Si}.