1
$\begingroup$

I'm trying to solve the following problem:

There are B (B is allowed to vary) 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?

$\endgroup$
1
$\begingroup$

The "known" subset-sum problem takes as input a list L of n integers and a target sum A.
Partition L into n lists (each containing one of the n integers).
Append a zero to each of the n lists.
Now, each list contains an integer from L and a $0$.

Now, feed the n lists and the target A into an algorithm that solves your problem. If your algorithm solves the problem in polynomial time, then it also solves the known subset problem in polynomial time.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.