Subset sum vs. Subset product (strong vs. weak NP hardness)

Question

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, but I guess it was less visible than their earlier claim in their book.

Answer 1

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

Answer 2

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.

<edit>

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

</edit>

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.

Answer 3

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.