0
$\begingroup$

We know that the "subset product problem" is NP-complete, as Gary and Johnson mentioned in their book, and the proof is by reduction from X3C.

I wonder if we can prove that this problem, i.e., the subset product problem is NP-complete even where all the given numbers are distinct powers of 2?

It seems to me it has to be NP-complete, but I have challenge with this, as in any reduction- if there is any- we need to create 2 to the power of the numbers that we are given which is not obtained in polynomial time. Does anybody have any idea?

$\endgroup$

migrated from cstheory.stackexchange.com May 13 '15 at 21:30

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 9
    $\begingroup$ If you allow a succinct representation (i.e. $2^{x_1 x_2 x_3}, 2^{x_4 x_5 x_6},...)$ then it is NP-complete and the reduction from X3C is immediate (practically the same reduction used for SUBSET SUM). Otherwise, without a succinct represeentation, it is in $P$ (simply strip off the exponents and you get a SUBSET SUM problem whose input size is logarithmic w.r.t the original input). $\endgroup$ – Vor May 6 '15 at 19:35
  • $\begingroup$ Thanks, but I don't know that much about succinct representations. Can you please explain more? Also, what do you mean by "the same reduction used for subset sum"? I guess you meant "the subset product", right? If you meant replacing each $x_i$ in the X3C problem by a power of 2, then the reverse side in the reduction does not work? $\endgroup$ – user24175 May 6 '15 at 20:43
  • 1
    $\begingroup$ The input of your problem is a list of powers of 2 and a target product $T$ (also a power of 2, otherwise we have trivial cases) e.g. 2,16,128,65536; T=32. If you allow a succinct representation, i.e. the inputs are "succinctly" represented by the exponents of those powers ( 1,4,7,16; T=5 ), then your problem is equivalent to the SUBSET SUM problem (e.g. $2^1 \cdot 2^4 = 2^{1+4} = T = 2^5$ $\sim 1+4=5$). $\endgroup$ – Vor May 6 '15 at 21:17
  • $\begingroup$ Thanks! Yes, exactly. I basically was looking at this problem as it is equivalent to the subset-sum problem. Since, as you said, it is equivalent to having the sum of the powers equal to the log(T). I need to know how can I work with this succinct representations. I came up with this problem, and then I realized, generally how can we analyze the problems that the input is exponential. Can you please give me a good reference for the succinct representations? I really need to learn about them more. $\endgroup$ – user24175 May 6 '15 at 21:50
  • $\begingroup$ I am sorry, but still I am not sure if I get how does your argument work: I assume that we have the representation of those numbers in terms of their powers, then I only need to work with the powers and their summation, instead of the the original numbers, is that right? So, you mean that if we know the powers, then the problem is algorithmically equivalent to the subset sum, and therefore is NP-complete? So, do I need to prove the reduction, or just saying this argument would be fine? $\endgroup$ – user24175 May 6 '15 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.