# Combining subset sum and subset product problems

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$.

• 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$). – R B Jan 12 '14 at 8:48
• Thank you, I see your point. We can assume that all set members are positive integers. – Dmitriy Finozhenok Jan 12 '14 at 9:30
• @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. – David Richerby Jan 12 '14 at 11:04
• @David Richerby, thank you for your help. – Dmitriy Finozhenok Jan 12 '14 at 14:54

## 1 Answer

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$.

• 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)? – Marzio De Biasi Jan 12 '14 at 19:23
• @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}$. – domotorp Jan 12 '14 at 20:08