Menu
I know that Knapsack is NP-complete while it can be solved by DP. They say that the DP solution is pseudo-polynomial, since it is exponential in the "length of input" (i.e. the numbers of bits required to encode the input). Unfortunately I did not get it. Can anybody explain that pseudo-polynomial thing to me slowly ?
683
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Therefore, the knapsack problem can be reduced to the Subset-Sum problem in polynomial time. . That is, if there is a way of rounding off the values making them more restricted, then we'd have a polynomial-time algorithm. This is to say that the non-deterministic part of the algorithm lies in the size of the input.
In this article, we talked about pseudo-polynomial algorithms. They are polynomial in the input's magnitude. However, as we illustrated with an example, such algorithms aren't polynomial in the number of bits we need to store their inputs.
Theorem 1 Knapsack is NP-complete. Proof: First of all, Knapsack is NP. The proof is the set S of items that are chosen and the verification process is to compute ∑i∈S si and ∑i∈S vi, which takes polynomial time in the size of input.
The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial.
Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the computational runtime uses the factor 1,000,000,000,000 which is O(240).
So the runtime is more accurately said to be O(N.2bits in W), which is exponential.
Also see:
105
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
