15
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Probably it'd be good to imagine how you would implement your dynamic programming algorithm. Then, you'd find what was wrong. $\endgroup$ – Yoshio Okamoto Mar 17 '13 at 12:42
  • $\begingroup$ @MohammadAl-Turkistany: Its in the final section of this column $\endgroup$ – RDN Mar 28 '13 at 13:12
5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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! $\endgroup$ – RDN Mar 28 '13 at 9:53
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Mar 22 '13 at 2:21
  • 1
    $\begingroup$ 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? $\endgroup$ – RDN Mar 25 '13 at 23:18
  • 1
    $\begingroup$ @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). $\endgroup$ – Alex ten Brink Mar 26 '13 at 21:37
  • $\begingroup$ 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. $\endgroup$ – vzn Mar 26 '13 at 22:37
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I understand that. My question was about why the conclusion I had made earlier was incorrect (i.e., equivalence of SS and SP). $\endgroup$ – RDN Mar 17 '13 at 17:24
  • $\begingroup$ @rdn There are not equivalent in that sense unless P =NP. $\endgroup$ – Mohammad Al-Turkistany Mar 17 '13 at 17:30
  • $\begingroup$ Yes, I get that. But I want to know what was wrong with my reductions in either direction. $\endgroup$ – RDN Mar 17 '13 at 17:33
  • $\begingroup$ Can you outline you reductions? $\endgroup$ – Mohammad Al-Turkistany Mar 17 '13 at 17:37
  • $\begingroup$ 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)$. $\endgroup$ – RDN Mar 17 '13 at 17:52

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.