0
$\begingroup$

Given n lists of m elements each we need to obtain sum S by selecting one element from each list. Is corresponding decision problem NP-complete? Are there papers about it?

$\endgroup$
1
$\begingroup$

I don't know if this problem has a name (yet), but it is at least weakly NP-hard since we can reduce subset sum to it:

Given a subset sum instance with item set $A = \{a_1,\ldots,a_n\}$ and target value $B$, we set $S = B$, $m = 2$, and create one list for each $a \in A$ with the two values $(a, 0)$. Basically, for each $a \in A$, you then have the choice to either take it (if you take $a$) or to not select it (if you take $0$). The requirement to "select one element from each list" is then translated into "you are allowed to pick each element at most once".

$\endgroup$
  • 1
    $\begingroup$ Why is this only a proof of weak NP-hardness, rather than NP-hardness (and therefore NP-completeness, since clearly the problem is in NP)? $\endgroup$ – Joppy Mar 19 '18 at 10:30
  • $\begingroup$ It is a proof of weak NP-hardness since Subset Sum is weakly NP-hard. This means that Subset Sum becomes solvable in polynomial time if the input numbers are encoded as unary numbers. I highly doubt that the given problem is also strongly NP-hard. And yes, as you said, this means also that it is NP-complete. $\endgroup$ – user1742364 Mar 19 '18 at 10:51

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.