1
$\begingroup$

I know that the subset sum problem is NP-Complete because I can reduce a known NP-Complete problem to subset sum.

However, since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete. I then realized that the dynamic programming solution in fact tries all possible combinations and because of this, is in fact the same as a brute force approach. Is this a valid insight into why subset sum is NP-Complete?

$\endgroup$
1
$\begingroup$

tries all possible combinations and because of this, is in fact the same as a brute force approach

You don't share the specific algorithm you have in mind, but I think you are wrong. Trying all splittings at every level of the recursion is not the same as trying all solutions.

since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete

Again, you don't share the specific algorithm, but it probably has pseudo-polynomial running time. So no, there is no contradiction; "dynamic programming" does not equal "polynomial time" let alone "fast".

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.