<p>Regarding the problem of equivalence of Subset Sum and Subset Product There is an technicality regarding Subset Product. Product of x's = T is actually Psuedopolynomial if T is not exponential! So the proofs of Subset Product being NP Hard are not (for technical reasons!!!) quite correct! </p>

<p>However given a promise that T is Large Then the reduction via Logarithms to Subset Sum gives a NONSTANDARD SUBSET SUM which is over the reals! This means that the Psuedopolynomial algorithm for Subset Sum Does not apply! Although the Logarithms are small, the decimal places messes up the Psuedopolynomial Dynamic Programming! </p>

<p>I hope this helps</p>

<p>Zelah</p>

CC BY-SA 3.0
2013-03-28T09:53:24.567Z
Turns out you were correct all along about the reductions being incorrect (i.e., claiming they show strong NP-completeness, when they do not). Thanks!
RDN
CC BY-SA 3.0
2013-03-21T12:15:31.447Z
2013-03-21T12:15:31.447Z
Zelah 02
<p>Firstly, using exponentiation to go from SS to SP works (using base 2 rather than base $e$), but blows up the size of the numbers involved. Weak NP-hardness means that if the numbers are small (or more precisely, denoted in unary), the problem is no longer hard. Hence, using exponentiation creates exponentially sized instances of SP even for the easy instances of SS, where the numbers are written in unary.</p>

<p>Secondly, using logarithms to go from SP to SS doesn't work, as logarithms typically generates non-integer values. SS and SP are defined using integer numbers, and logarithms often result in transcendental values, which are hard to represent or do math on.</p>

<pre><code>&lt;edit&gt;
</code></pre>

<p>Let $A$ be an integer, $A &gt; 0$, then $\log_2 A$ is rational if and only if $A$ is a power of 2, and transcendental otherwise. Firstly, if $\log_2 A = \frac{p}{q}$ for nonzero integers $p$ and $q$, then $A = 2^{\frac{p}{q}}$, $A^q = 2^p$. We therefore have that $A = 2^r$ by prime decomposition. Furthermore $A^{rq} = 2^p$, so given an $A$ we can pick $q=1$ and $p=r$ to prove $\log_2 A$ is rational.</p>

<p>We just need to show that $\log_2 A$ is never transcendental otherwise. This follows from the <a href="http://en.wikipedia.org/wiki/Gelfond%E2%80%93Schneider_theorem" rel="nofollow">Gelfond-Schneider theorem</a>, for an equivalent formulation (as can be found on the Wiki page) is "if $\alpha$ and $\gamma$ are nonzero algebraic numbers, and we take any non-zero logarithm of $\alpha$, then $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ is either rational or transcendental." It is also easy to verify by taking the converse of the theorem and setting $\alpha^\beta = \gamma$ and hence $\beta = \log_\alpha \gamma$.</p>

<pre><code>&lt;/edit&gt;
</code></pre>

<p>Lastly, consider what happens when we try the dynamic programming algorithm from SS on SP. Because we use products rather than sums, the numbers involved blow up enormously, and the arbitrary precision math required suddenly becomes a factor in the running time. This is why the algorithm cannot solve SP instances quickly even if the numbers are in unary.</p>

CC BY-SA 3.0
2013-03-22T02:21:46.003Z
this leads to a somewhat interesting special case. for what class of numbers are the log's expressible as rationals and not requiring infinite precision? in this case the problems would indeed be nearly equivalent & reducible to each other. it also seems to lead toward a "natural" approximation algorithm.
vzn
CC BY-SA 3.0
2013-03-25T23:18:03.497Z
Thanks for the great answer! I have just one issue -- I get why taking logs is illegal (except perhaps in the case where the logs are poly in length -- as vzn points out), but I'm still unsure about the legality of going from SS to SP via exponentiation.

WRT going from SS to SP as you mentioned (via exponentiation), don't we run into the following problem: The number of bits in the input instance of $I_{SS}$ is $O(n\log x)$ and the number of bits in the instance of $I_{SP}$ is $O(nx)$. This is an exponential blow-up. So is it still legal? If it is, why?
RDN
CC BY-SA 3.0
2013-03-26T21:37:03.007Z
@vzn, RDN: I edited in a characterization when the logarithm is transcendental. About the blow-up in the reduction, it depends on your definition of 'legal': the reduction is *correct*, yet its efficiency is not polynomial, and hence does not say anything about NP-hardness. It is therefore not a correct *poly-time* reduction, but it is a correct reduction (without qualifiers).
Alex ten Brink
CC BY-SA 3.0
2013-03-26T22:37:36.470Z
also there is a special case where all numbers are in the form $c^{n_i}$, each $n_i$ rational, for any $c$, not just $c=2$. the approximation algorithm I was thinking of might find a $c$ such that the conversion of values into that "base" is "close" to the originals.
vzn
CC BY-SA 3.0
2013-03-17T19:09:00.513Z
2013-03-26T21:32:14.563Z
2013-03-26T21:32:14.563Z
Alex ten Brink
<p>The literal explanation is that Subset Product problem is NP-complete by a reduction from strongly NP-complete problem such as exact cover by 3-sets. In such "strong" reduction, the input integers are bounded by some polynomial function in the number of integers in the resulting instance of Subset Product problem. </p>

<p>Such a "strong" reduction is impossible from any strongly NP-complete problem to Subset Sum Problem unless $P=NP$. We have polynomial-time dynamic programming algorithm for solving Subset Sum problem if input integers are bounded by a polynomial.</p>

CC BY-SA 3.0
2013-03-17T17:24:30.750Z
Yes, I understand that. My question was about why the conclusion I had made earlier was incorrect (i.e., equivalence of SS and SP).
RDN
CC BY-SA 3.0
2013-03-17T17:30:13.233Z
@rdn There are not equivalent in that sense unless P =NP.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-03-17T17:33:34.237Z
Yes, I get that. But I want to know what was wrong with my reductions in either direction.
RDN
CC BY-SA 3.0
2013-03-17T17:37:56.247Z
Can you outline you reductions?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-03-17T17:52:00.557Z
Let $I(SS)=\langle X, S \rangle$ be an instance of SS and $I(SP)=\langle Y, P \rangle$ be an instance of SP. Transforming $I(SS)$ into $I(SP)$: Let $P = e^S$ and $Y_i = e^{X_i}$. There exists a SS of sum $S$ iff there exists a SP of product $P = e^S$.                     Transforming $I(SP)$ into $I(SS)$: Let $S = log(P)$ and $X_i = \log(Y_i)$. There exists a SP of product $P$ iff there exists a SS of sum $S = \log(P)$.
RDN
CC BY-SA 3.0
2013-03-17T12:57:22.307Z
2013-03-17T13:07:13.710Z
2013-03-17T13:07:13.710Z
Mohammad Al-Turkistany
<p>I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard.</p>
<p>Subset Sum: Given <span class="math-container">$X = \{x_1,...,x_n\}$</span> and <span class="math-container">$T$</span>, does there exist a subset <span class="math-container">$X'$</span> such that <span class="math-container">$\sum_{i\in X'}x_i = T$</span>.</p>
<p>Subset Product: Given <span class="math-container">$X = \{x_1,...,x_n\}$</span> and <span class="math-container">$T$</span>, does there exist a subset <span class="math-container">$X'$</span> such that <span class="math-container">$\prod_{i\in X'}x_i = T$</span>.</p>
<p>I always thought the two problems were equivalent -- an instance of SS could be transformed to an instance of SP via exponentiation and an instance of SP to SS via logarithms. This led me to conclude that they both belonged to the same class of NP-hard -- i.e., they were both weakly NP-hard.</p>
<p>Further, it appears that the same recurrence could be used to solve both problems using dynamic programming with a very small change (replacing subtraction in SS with division in SP).</p>
<p>That was until I read chapter 8 of &quot;Theory of Computation&quot; by Bernard Moret (for those without the book, it has a proof of hardness of subset product via X3C -- a strongly NP-hard problem).</p>
<p>I understand the reduction, but cannot figure out what was wrong with my earlier conclusion (equivalence of the two problems).</p>
<hr />
<p><strong>UPDATE</strong>: Turns out that subset product is only weakly NP-complete (the target product is exponential in <span class="math-container">$\Omega (n)$</span>). Gary and Johnson published this in their <a href="https://web.archive.org/web/20130512145415/http://www2.research.att.com/%7Edsj/columns/col1.pdf" rel="nofollow noreferrer">NP-completeness column in 1981</a>, but I guess it was less visible than their earlier claim in their book.</p>

CC BY-SA 3.0
2013-03-17T12:42:38.733Z
Probably it'd be good to imagine how you would implement your dynamic programming algorithm. Then, you'd find what was wrong.
Yoshio Okamoto
CC BY-SA 3.0
2013-03-28T13:12:52.887Z
@MohammadAl-Turkistany: Its in the final section of this [column](http://www2.research.att.com/~dsj/columns/col1.pdf)
RDN
CC BY-SA 4.0
2024-02-20T12:48:38.357Z
The saving grace here is that **Product Partition** *is* strongly NP-hard.  See [this paper](https://doi.org/10.1016/j.ejor.2010.05.034) (pdf [here](https://www.academia.edu/download/43201009/Product_Partition_and_related_problems_o20160229-21348-v6931k.pdf)). Product Partition is, given integers $(w_1, \ldots, w_n)$, to determine whether there is a subset $S\subseteq [n]$ such that $\prod_{i\in S} w_i = \prod_{i\in [n]\setminus S} w_i$.  (The obvious reduction to Subset Product fails because, when the $w_i$'s are polynomial in $n$ and given in unary, their product is not polynomial in $n$. )
Neal Young
<cc.complexity-theory><np-hardness><reductions><subset-sum>
Subset sum vs. Subset product (strong vs. weak NP hardness)
RDN
# Subset sum vs. Subset product (strong vs. weak NP hardness)

(Asked by: username_0 on 2013-03-17)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard.

Subset Sum: Given $X = \{x\_1,...,x\_n\}$ and $T$, does there exist a subset $X'$ such that $\sum\_{i\in X'}x\_i = T$.

Subset Product: Given $X = \{x\_1,...,x\_n\}$ and $T$, does there exist a subset $X'$ such that $\prod\_{i\in X'}x\_i = T$.

I always thought the two problems were equivalent -- an instance of SS could be transformed to an instance of SP via exponentiation and an instance of SP to SS via logarithms. This led me to conclude that they both belonged to the same class of NP-hard -- i.e., they were both weakly NP-hard.

Further, it appears that the same recurrence could be used to solve both problems using dynamic programming with a very small change (replacing subtraction in SS with division in SP).

That was until I read chapter 8 of "Theory of Computation" by Bernard Moret (for those without the book, it has a proof of hardness of subset product via X3C -- a strongly NP-hard problem).

I understand the reduction, but cannot figure out what was wrong with my earlier conclusion (equivalence of the two problems).

---

**UPDATE**: Turns out that subset product is only weakly NP-complete (the target product is exponential in $\Omega (n)$). Gary and Johnson published this in their [NP-completeness column in 1981](https://web.archive.org/web/20130512145415/http://www2.research.att.com/%7Edsj/columns/col1.pdf), but I guess it was less visible than their earlier claim in their book.

**Tags:** cc.complexity-theory, np-hardness, reductions, subset-sum

> **Comments:**
> **username_1**: Probably it'd be good to imagine how you would implement your dynamic programming algorithm. Then, you'd find what was wrong.  
> **username_0**: @MohammadAl-Turkistany: Its in the final section of this [column](http://www2.research.att.com/~dsj/columns/col1.pdf)  
> **username_2**: The saving grace here is that **Product Partition** *is* strongly NP-hard.  See [this paper](https://doi.org/10.1016/j.ejor.2010.05.034) (pdf [here](https://www.academia.edu/download/43201009/Product_Partition_and_related_problems_o20160229-21348-v6931k.pdf)). Product Partition is, given integers $(w_1, \ldots, w_n)$, to determine whether there is a subset $S\subseteq [n]$ such that $\prod_{i\in S} w_i = \prod_{i\in [n]\setminus S} w_i$.  (The obvious reduction to Subset Product fails because, when the $w_i$'s are polynomial in $n$ and given in unary, their product is not polynomial in $n$. )  

---

## 3 answers

### Answer by username_3 on 2013-03-21. Score: 5 | Accepted answer

Regarding the problem of equivalence of Subset Sum and Subset Product There is an technicality regarding Subset Product. Product of x's = T is actually Psuedopolynomial if T is not exponential! So the proofs of Subset Product being NP Hard are not (for technical reasons!!!) quite correct!

However given a promise that T is Large Then the reduction via Logarithms to Subset Sum gives a NONSTANDARD SUBSET SUM which is over the reals! This means that the Psuedopolynomial algorithm for Subset Sum Does not apply! Although the Logarithms are small, the decimal places messes up the Psuedopolynomial Dynamic Programming!

I hope this helps

Zelah

> **Comments:**
> **username_0**: Turns out you were correct all along about the reductions being incorrect (i.e., claiming they show strong NP-completeness, when they do not). Thanks!  

---

### Answer by username_4 on 2013-03-17. Score: 10

Firstly, using exponentiation to go from SS to SP works (using base 2 rather than base $e$), but blows up the size of the numbers involved. Weak NP-hardness means that if the numbers are small (or more precisely, denoted in unary), the problem is no longer hard. Hence, using exponentiation creates exponentially sized instances of SP even for the easy instances of SS, where the numbers are written in unary.
Secondly, using logarithms to go from SP to SS doesn't work, as logarithms typically generates non-integer values. SS and SP are defined using integer numbers, and logarithms often result in transcendental values, which are hard to represent or do math on.


Let $A$ be an integer, $A > 0$, then $\log_2 A$ is rational if and only if $A$ is a power of 2, and transcendental otherwise. Firstly, if $\log_2 A = \frac{p}{q}$ for nonzero integers $p$ and $q$, then $A = 2^{\frac{p}{q}}$, $A^q = 2^p$. We therefore have that $A = 2^r$ by prime decomposition. Furthermore $A^{rq} = 2^p$, so given an $A$ we can pick $q=1$ and $p=r$ to prove $\log_2 A$ is rational.
We just need to show that $\log_2 A$ is never transcendental otherwise. This follows from the Gelfond-Schneider theorem, for an equivalent formulation (as can be found on the Wiki page) is "if $\alpha$ and $\gamma$ are nonzero algebraic numbers, and we take any non-zero logarithm of $\alpha$, then $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ is either rational or transcendental." It is also easy to verify by taking the converse of the theorem and setting $\alpha^\beta = \gamma$ and hence $\beta = \log_\alpha \gamma$.


Lastly, consider what happens when we try the dynamic programming algorithm from SS on SP. Because we use products rather than sums, the numbers involved blow up enormously, and the arbitrary precision math required suddenly becomes a factor in the running time. This is why the algorithm cannot solve SP instances quickly even if the numbers are in unary.

> **Comments:**
> **username_5**: this leads to a somewhat interesting special case. for what class of numbers are the log's expressible as rationals and not requiring infinite precision? in this case the problems would indeed be nearly equivalent & reducible to each other. it also seems to lead toward a "natural" approximation algorithm.  
> **username_0**: Thanks for the great answer! I have just one issue -- I get why taking logs is illegal (except perhaps in the case where the logs are poly in length -- as username_5 points out), but I'm still unsure about the legality of going from SS to SP via exponentiation.  WRT going from SS to SP as you mentioned (via exponentiation), don't we run into the following problem: The number of bits in the input instance of $I_{SS}$ is $O(n\log x)$ and the number of bits in the instance of $I_{SP}$ is $O(nx)$. This is an exponential blow-up. So is it still legal? If it is, why?  
> **username_4**: @username_5, username_0: I edited in a characterization when the logarithm is transcendental. About the blow-up in the reduction, it depends on your definition of 'legal': the reduction is *correct*, yet its efficiency is not polynomial, and hence does not say anything about NP-hardness. It is therefore not a correct *poly-time* reduction, but it is a correct reduction (without qualifiers).  
> **username_5**: also there is a special case where all numbers are in the form $c^{n_i}$, each $n_i$ rational, for any $c$, not just $c=2$. the approximation algorithm I was thinking of might find a $c$ such that the conversion of values into that "base" is "close" to the originals.  

---

### Answer by username_6 on 2013-03-17. Score: 1

The literal explanation is that Subset Product problem is NP-complete by a reduction from strongly NP-complete problem such as exact cover by 3-sets. In such "strong" reduction, the input integers are bounded by some polynomial function in the number of integers in the resulting instance of Subset Product problem.

Such a "strong" reduction is impossible from any strongly NP-complete problem to Subset Sum Problem unless $P=NP$. We have polynomial-time dynamic programming algorithm for solving Subset Sum problem if input integers are bounded by a polynomial.

> **Comments:**
> **username_0**: Yes, I understand that. My question was about why the conclusion I had made earlier was incorrect (i.e., equivalence of SS and SP).  
> **username_6**: @rdn There are not equivalent in that sense unless P =NP.  
> **username_0**: Yes, I get that. But I want to know what was wrong with my reductions in either direction.  
> **username_6**: Can you outline you reductions?  
> **username_0**: Let $I(SS)=\langle X, S \rangle$ be an instance of SS and $I(SP)=\langle Y, P \rangle$ be an instance of SP. Transforming $I(SS)$ into $I(SP)$: Let $P = e^S$ and $Y_i = e^{X_i}$. There exists a SS of sum $S$ iff there exists a SP of product $P = e^S$.                     Transforming $I(SP)$ into $I(SS)$: Let $S = log(P)$ and $X_i = \log(Y_i)$. There exists a SP of product $P$ iff there exists a SS of sum $S = \log(P)$.  

---

