SUBSET-SUM-kS, t> | S-(X1 equals t). For example, is in SUBSET-SUM because 3+7+11-21. SET-PARTITION = { S = {xi Xk} can be partitioned into two parts A and A whereA XkJand for some {y yh} {X1 Xk} the sum of the y's . S - A and the sum of the elements in A is equal to the sum of the elements in -A. For example, works because A 12, 3,7] and -A-4, 8] since 2+3+7-4+8 a) Prove that SUBSET-SUM is in NFP. b) Prove that SET-PARTITION is in NP I claim that SET-PARTITION is NP-complete and so if it reduces to SUBSET-SUM then SUBSET-SUM is NP-complete too. So I need to show that SET-PARTITION sp SUBSET SUM. My reduction function is 1. Add up X1 Xk and to get y 2. If y is even then t-y/2 otherwise t = 0 3. Output c) Either give a counter example or use the definition for sp to explain why my reduction function F either does or does not work? d) Prove my claim that, if SET-PARTITION is NP-complete and if it reduces to SUBSET- SUM then SUBSET-SUM is NP-complete. SUBSET-SUM-kS, t> | S-(X1 equals t). For example, is in SUBSET-SUM because 3+7+11-21. SET-PARTITION = { S = {xi Xk} can be partitioned into two parts A and A whereA XkJand for some {y yh} {X1 Xk} the sum of the y's . S - A and the sum of the elements in A is equal to the sum of the elements in -A. For example, works because A 12, 3,7] and -A-4, 8] since 2+3+7-4+8 a) Prove that SUBSET-SUM is in NFP. b) Prove that SET-PARTITION is in NP I claim that SET-PARTITION is NP-complete and so if it reduces to SUBSET-SUM then SUBSET-SUM is NP-complete too. So I need to show that SET-PARTITION sp SUBSET SUM. My reduction function is 1. Add up X1 Xk and to get y 2. If y is even then t-y/2 otherwise t = 0 3. Output c) Either give a counter example or use the definition for sp to explain why my reduction function F either does or does not work? d) Prove my claim that, if SET-PARTITION is NP-complete and if it reduces to SUBSET- SUM then SUBSET-SUM is NP-complete