> I just found a final on Exambank, and I was wondering about question
> five. The problem is worth 10 marks out of 60 total on the exam.
>
> It reads:
>
> Given two sets of natural numbers, A and B, are there non-empty
> subsets A' of A and B' of B such that sum(A') = sum(B')? Let n be the
> number of elements in A, and m be the number of elements in B. Let's
> call this SMALL-PARTITION.
>
> The task is to prove that this is NP complete.
>
> Clearly, the problem is in NP since we can compute the sums in O(n +
> m) time.
>
> To prove it's complete, I thought that the easiest would be to prove
> that SUBSET-SUM <=p DUAL-PARTITION, and here's what I did:
>
> Given an instance of SUBSET-SUM over a set C with a target sum s,
> construct the instance of DUAL-PARTITION as follows:
>
> Let A be the set C, and let B be a set with the single element 's' in
> it. This reduction is clearly polytime.
>
> Then,
> 1. If SUBSET-SUM has a subset that sums to s, our DUAL-PARTITION
> oracle returns yes, since it will find a subset of A that sums to s.
> 2. If DUAL-PARTITION is able to make A' and B' such that sum(A') =
> sum(B') = s, then A' is a subset of C that works.
>
> So, DUAL-PARTITION is NPC.
>
> This seems like a really cheap way to do this, so I suspect I'm wrong.
> Am I?
>
> Thanks,
> Martin.