I'm trying to solve the following problem:

There are B lists of unspecified size containing integers. Pick a number from each list so that the sum of all the picks is exactly A. Prove that this problem is NP complete by reducing the known NP complete subset sum problem.

My thinking on how to solve this: First one has to "limit" the normal subset sum problem by only making subsets of size B acceptable, so one has to start by reducing the common subset problem to a fixed size subset problem in polynomial time. I'm not quite sure how to do this tough.

Secondly I was thinking that you could make all the lists in the problem copies of the set (e.g. if the set is {1,2,3,4,5}, all the lists will be {1,2,3,4,5}), so that each list pick represents a number in the set. The problem with this thinking is that there is nothing preventing you from picking the same number twice, while the normal subset sum problem only allows you to use the same number once. I also dont think that there is a way to arrange the lists so that this is impossible to do. Because of this, I'm not sure that I'm on the right track in my thinking. It is also possible that the subset sum problem can be reduced to allowing choosing the same number more than once, but I'm not sure how that can be done. Ideas?

  • $\begingroup$ I think this is more suited for cs or math Stackexchange forums. The reduction I'm thinking of is either too easy to reveal here, or is completely wrong; I suspect it is not wrong. $\endgroup$ – The Masked Avenger Nov 19 '14 at 0:55
  • $\begingroup$ If B is fixed, say B=7, then there is a polynomial time algorithm: try all allowed sums. This is bounded above by Mn^7, where n is how many numbers on all the lists and M is an upper bound on the time to evaluate a sum. So if B is not allowed to vary, I do not see how you will show it is NP-complete. $\endgroup$ – The Masked Avenger Nov 19 '14 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.