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

CC BY-SA 3.0
2014-01-12T19:23:39.570Z
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
CC BY-SA 3.0
2014-01-12T20:08:34.223Z
@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
CC BY-SA 3.0
2014-01-12T18:40:12.043Z
2014-01-12T18:40:12.043Z
domotorp
<p>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$.</p>

CC BY-SA 3.0
2014-01-12T08:48:27.800Z
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
CC BY-SA 3.0
2014-01-12T09:30:01.917Z
Thank you, I see your point. We can assume that all set members are positive integers.
Dmitriy Finozhenok
CC BY-SA 3.0
2014-01-12T11:04:46.413Z
@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
CC BY-SA 3.0
2014-01-12T14:54:30.720Z
@David Richerby, thank you for your help.
Dmitriy Finozhenok
<cc.complexity-theory><subset-sum>
Combining subset sum and subset product problems
Dmitriy Finozhenok
# Combining subset sum and subset product problems

(Asked by: username_0 on 2014-01-12)

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

**Tags:** cc.complexity-theory, subset-sum
> **Comments:**
> **username_1**: 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$).  
> **username_0**: Thank you, I see your point. We can assume that all set members are positive integers.  
> **username_2**: @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.  
> **username_0**: @David Richerby, thank you for your help.  

---

## 1 answers

### Answer by username_3 on 2014-01-12. Score: 3 | Accepted 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$.

> **Comments:**
> **username_4**: 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)?  
> **username_3**: @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}$.  

---

