Question

So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard.

The given problem I have is subset sum.

However, the conditions have been change to sum ≤ M and sum ≥ M from sum = M. To be more specific:

  1. "If we ask if there is a subset with sum ≤ M, is the problem still NP- Complete?"

  2. "If we ask if there is a subset with sum ≥ M, is the problem still NP- Complete?"

My initial reaction is that the two problems are no longer NP-complete since they can both be solved within polynomial time.

  1. Check each element and see if there exists at least one smaller than M.
  2. Add all positive integers and see if the sum of all elements is larger than M.

Since it isn't NP Hard, it cannot therefore be NP-complete.

Am I thinking/approaching this correctly?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top