5
$\begingroup$

The subset sum problem and subset product problem are NP-complete. Is the following problem polynomial-time solvable: given a set of positive integers, find a subset whose sum is $S$ and whose product is $T$.

$\endgroup$
  • 5
    $\begingroup$ The problem is NP-complete if you allow $0$'s: (showing <subset sum -> your problem> reduction). Suppose you have a subset sum instance $<I,k>$ (i.e. needs to decide whether there's a subset $S$ of $I$ whose sum is $k$). Now ask if $<I\cup\{0\},k,0>$ is a part of your language (i.e. whether $I\cup\{0\}$ has a subset whose sum is $k$ and product is $0$). $\endgroup$ – R B Jan 12 '14 at 8:48
  • $\begingroup$ Thank you, I see your point. We can assume that all set members are positive integers. $\endgroup$ – Dmitriy Finozhenok Jan 12 '14 at 9:30
  • 4
    $\begingroup$ @DmitriyFinozhenok The question should always contain all the important information so people don't have to read the comments to find them. I edited your question to include the assumption that we're dealing with positive integers. $\endgroup$ – David Richerby Jan 12 '14 at 11:04
  • 1
    $\begingroup$ @David Richerby, thank you for your help. $\endgroup$ – Dmitriy Finozhenok Jan 12 '14 at 14:54
3
$\begingroup$

It is still NP-complete. Here is a very sketchy reduction from subset sum. The goal of the whole reduction will be to make $T$ unimportant. If the inputs for subset sum are $a_i$, then add $a_i$ and $2^Na_i$ to our inputs, where $N$ is large, but still $poly(n)$. Set $S$ to be $2^N$ times the original subset sum plus $2^N-1$. Set $T$ to be the product of the $a_i$'s multiplied by a sufficiently big power of $2$, to be determined later. The idea is that if the number with index $i$ was not picked, then we can pick $a_i$, while if it was picked, we can pick $2^Na_i$. Finally, add a lot of each small power of $2$ to our input to be able to make the desired sum and product. Notice that this gives us enough liberty to get $S$ and $T$.

$\endgroup$
  • 1
    $\begingroup$ I'm trying to understand the reduction; can you give a small example: suppose that $a_1=010$ (2), $a_2=011$ (3), $a_3=100$ (4), target_sum=101 (5); we can pick for example N=4 (it should be large enough) and set S = 1010000 + 0001111 = 1011111; the new elements $a_i$ and $2^N a_i$ are 0100000,0110000,1000000,010,011,100: what are the additional small powers of 2? And what is the target product T (which should be independant from the choice of the $a_i$s)? $\endgroup$ – Marzio De Biasi Jan 12 '14 at 19:23
  • $\begingroup$ @Marzio: sorry but I have not worked out the details. T should be 12 times a very large 2 power and we add many-many powers of 2 to the input, but only small ones, say $<2^{2n}$ where each $a_i$ has at most $n$ digits. $N$ would be say $n^4$, so quite unreachable with these sums. Hm, maybe better make the "plus" part of $S$ only $2^{2n}$. $\endgroup$ – domotorp Jan 12 '14 at 20:08

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.