I know that dynamic programming is used to solve in "pseudo-polynomial time" some NP problems, like the knapsack. If P = NP, would it mean that every problem that we solve with dynamic programming would have a more efficient (polynomial) way to solve? Or are there problems that even if P = NP, we would still use dynamic programming

  • $\begingroup$ dynamic programming is only a "trick" to solve complex problems. $\endgroup$
    – nir shahar
    Apr 18, 2021 at 20:06

1 Answer 1


Absolutely not. P = NP doesn't imply that problems that can be solved with dynamic programming can be solved easier or quicker with another algorithm.

  • $\begingroup$ Can you elaborate more? Does that mean that only some problems that can be solved with dynamic programming would have a quicker algorithm? Doesn't by definition, if P = NP, the knapsack problem would have a polynomial time algorithm, which must be more efficient than the usual dynamic programming approach? $\endgroup$ Apr 18, 2021 at 22:34
  • $\begingroup$ @user14789259 Complexity analysis ignores coefficients. But actual performance can sometimes be dominated by this. $\endgroup$
    – Barmar
    Apr 19, 2021 at 6:10

Your Answer

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

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