6
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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, 2017 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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