4. Given that PARTITION problem (described below) is a NP-Complete problem, prove that the SUM OF SUBSETS problem (described below) is NP-Complete by reducing PARTITION problem to it. PARTITION: Instance: A finite set of positive integers Z= { 1, =2, ..., =n}. Question: Is there a subset Z' of Z such that Sum of all numbers in Z' = Sum of all numbers in Z-Z' SUM OF SUBSETS: Instance: A finite set of positive integers A = { a1, a2, ..., am} and M. Question: Is there a subset A' in A s.t. a = M? a; in A' (a) Give a nondeterministic polynomial time algorithm for the SUM OF SUBSETS problem. (b) Define the transformation from the PARTITION problem to the SUM OF SUBSETS problem. (c) Explain that the transformation described in part (b) satisfies: if the partition problem has a solution then the sum-of-subsets has a solution, and vice versa.