Urbanowicz's blog

By Urbanowicz, 10 years ago, In English

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:

  1. Is there direct way to reduce the problem to SSP?
  2. Is there any estimations of the minimal possible overhead of transformations?
  3. Or maybe there is pseudo-polynomial algorithm for the original problem?

Thank you in advance.

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

10 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I doubt there is a direct straightforward reduction.