Karp reduction from PARTITION to SUBSET SUM

Question

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?

Answer 1

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)