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?
Subset product problem for powers of 2
complexity theory