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.

On Aug 6, 3:38 pm, Martin gmail.com> wrote: