Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Subset product

  1. Jul 17, 2010 #1
    The subset sum problem is NP complete. What if we replace summing with multiplying? Would it still be np complete?
  2. jcsd
  3. Jul 17, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    Yes, else the subset sum problem wouldn't be NP-hard (take logs).
  4. Jul 18, 2010 #3
    Good point.
    Last edited: Jul 18, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook