PARTITION: Given a set of positive integers A={a_1,...,a_n} does there exist a subset of A with sum equal to the sum of it's complement?
SUBSET SUM: Given a set of positive integers A={a_1,...,a_n} and another positive integer B, does there exist a subset of A such that it's sum is equal to B?
I was trying to prove that if PARTITION is NP-complete then SUBSET SUM is also NP-complete, by reducing PART to SSUM.
My solution was: let A={a1,...,an} be a set of positive integers. Then if A when fed into PART gives the solution I={k1,...,km} (where k_i are the indices of the members of the solution subset), then we construct A'={a1,...an,S} where S is the sum of {a_k1,a_k2,...,a_km}. A' is a solution to SSUM.
My problem with this is that this goes only one way, meaning that we can't show that given A' then A is a solution to PART. Is this a problem? and how could i modify the proof to cover it?
Partition to SubsetSum is actually easier than what you've done here.
If Partition is Satisfied that means that there are some subsets P1 and P2 such that sum(P1) = sum(P2) correct? Because sum(P1) + sum(P2) = Sum(A), which means that sum(P1) = sum(P2) = (1/2)sum(A)
We don't even need to construct an A' for subset sum. Just set A' = A and the target sum = (1/2)sum(A). It should be clear that this is the exact same problem as Partition with almost no abstraction.
In other words Partition is always just subset sum where target sum = (1/2)sum(A)