Prove that SUBSET-SUM is NP-complete.

1. Prove that SUBSET-SUM is NP-complete. - Show that SUBSET-SUM is in NP. - Prove that 3-SAT p SUBSET-SUM. SUBSET-SUM: given natural numbers w1,,wn and an integer W, is there a subset that adds up to exactly W ? Ex: {1,4,16,64,256,1040,1041,1093,1284,1344},W=3754. Yes. 1+16+64+256+1040+1093+1284=3754