HiveBrain v1.2.0
Get Started
← Back to all entries
principleModerate

If a problem is in P solved via dynamic programming, is it also in NP?

Submitted by: @import:stackexchange-cs··
0
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?

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 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.