principleModerate
If a problem is in P solved via dynamic programming, is it also in NP?
Viewed 0 times
problemprogrammingalsoviadynamicsolved
Problem
So I can solve a given problem using dynamic programming in $O(n^2k^2)$ time complexity. This means that the problem is in P. But I am asked if it is in NP.
My answer is, "Since it is also polynomial time solvable, the problem is also in $NP$".
Is that a correct statement? If not, is a problem in P solved via dynamic programic also NP?
My answer is, "Since it is also polynomial time solvable, the problem is also in $NP$".
Is that a correct statement? If not, is a problem in P solved via dynamic programic also NP?
Solution
Any problem in P is also in NP
A decision problem that's in P is also in NP, because you can give the verification logic like this: for yes instance
Note that, the order written as $n^2 k^2$ doesn't simply mean the problem is in P (Check "Pseudo-polynomial time" in wikipedia.) For example, Knapsack problem can be solved by the dynamic programming and its order is $O(n W)$ where $n$ is the number of products and $W$ is the maximum weight for the knapsack. But $W$ is actually considered exponential of the input size and Knapsack problem is known to be NP-complete.
A decision problem that's in P is also in NP, because you can give the verification logic like this: for yes instance
x, use empty string as a certificate, and solve x in polynomial time. You get the result that it's yes instance (that's by definition of P) and that means verification is done in polynomial time. Note that, the order written as $n^2 k^2$ doesn't simply mean the problem is in P (Check "Pseudo-polynomial time" in wikipedia.) For example, Knapsack problem can be solved by the dynamic programming and its order is $O(n W)$ where $n$ is the number of products and $W$ is the maximum weight for the knapsack. But $W$ is actually considered exponential of the input size and Knapsack problem is known to be NP-complete.
Context
StackExchange Computer Science Q#118437, answer score: 19
Revisions (0)
No revisions yet.