5
$\begingroup$

Dynamic Programming seems to result in good performance algorithms for Weakly NP-hard Problems. Two examples are Subset Sum Problem and 0-1 Knapsack Problem, both problems are solvable in pseudo-polynomial time using Dynamic Programming. It turns out this is a pretty good result in most cases.

On the other hand, Strongly NP-hard Problems seem to be essentially exponential even by using Dynamic Programming. For example, the Multiple 0-1 Knapsack Problem (page 11).

Is this a true claim if I generalize my observations and state Dynamic Programming is good for Weakly NP-hard Problems but it is not suitable for Strongly NP-hard Problems?

$\endgroup$
4
$\begingroup$

You're generalizing too much from a small sample size. There is no guarantee that all weakly NP-complete problems can be solved using dynamic programming; I'd expect probably there are some that dynamic programming isn't much good for.

And, there is no guarantee that a strongly NP-hard problem will take exponential time to solve. There are NP-complete problems that can be solved faster than exponential time. (See also the exponential time hypothesis.)

Dynamic programming is just one algorithmic technique among many. There's nothing magical about it, and it's not a be-all and end-all. There are other algorithmic methods other than dynamic programming.

$\endgroup$
  • 1
    $\begingroup$ If multiple knapsack is SNP-hard, then under assumption of ETH correctness, it can't be solved in subexponential time. But I don't know if multiple knapsack is SNP-hard. $\endgroup$ – rus9384 Jun 28 '17 at 0:24
  • $\begingroup$ I know I can claim anything but it does not mean the truth. This is the reason of the question "Is this a true claim if I...". Anyway, I though this could be some kind of property/ limitation of DP, but it seems it is not the case at all. $\endgroup$ – André Gomes Jun 29 '17 at 15:39

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.