Consider the following problem. Given a finite set S of integers and k numbers b1, b2, ..., bk, is there any partition {B1, B2, ..., Bk} of S such that sum of all integers in Bi is equal to bi for all i = 1... k?
Obviously, this problem is in NP and NP-complete, because it is able to solve Subset Sum Problem instances by assigning k = 2. Although turning SSP into this problem is trivial, I cannot see any direct way to perform reverse transformation. (It is well-known that every NPC problem can be reduced to another NPC within polynomial time.)
I tried to follow Cook's theorem proof: I've built Circuit-SAT instance that verifies solution and successively reduced it to SSP through 3-SAT. Of course, I've got desired SSP instance, but it was over 9000 larger than original problem's one, rendering pseudo-polynomial algorithms unusable (to say the least). So, here's my questions:
- Is there direct way to reduce the problem to SSP?
- Is there any estimations of the minimal possible overhead of transformations?
- Or maybe there is pseudo-polynomial algorithm for the original problem?
Thank you in advance.