NP-Complete Reduction for Subset Sum

Question

I'm studying for a final exam and one of the practice problems given to us from a past exam is as follows:

My instinct says to reduce this problem to the Subset Sum problem.

My initial solution is:

Let 'A' be the Subset Sum NP-Complete problem.

Let 'B' be the Partition Problem that we are trying to prove is NP-Complete

'A' takes an instance alpha that is: a set S and a value 'b'

'B' takes an instance beta that is: a set S' and a k value for the decision

We want to polynomially reduce alpha to an instance beta

I would take b from alpha, put it into the set S to make S', then set k = 0 making beta equal to: S'=S union 'b', K = 0

Let's assume 'B' can solve for this instance. Since it can, it produces an output using beta which was formed from alpha.

Since 'B' can solve that instance, it means that 'A' is solvable in polynomial time, however we know this not to be true since 'A' is NP-Complete. We have a contradiction. Because of this contradiction, we know that 'B' is at least as 'hard' as 'A', therefore it too is NP complete.

Please let me know what's wrong with my solution or if it is valid.

Thanks

Answer 1

Actually this problem is (minimizing difference) is NP-hard. The decision version (not to be confused with decision problem, which you are) is whether there exists a solution that partitions so that the difference is zero, which is a NP-complete problem.

See http://en.wikipedia.org/wiki/Partition_problem

Excerpt from wiki page: There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard.