Subset with modified condition, is it still NP-complete? [closed]
-
05-11-2019 - |
Pregunta
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:
"If we ask if there is a subset with sum ≤ M, is the problem still NP- Complete?"
"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.
- Check each element and see if there exists at least one smaller than M.
- 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 hay solución correcta
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange