On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to $\log W$, where, I believe, $W$ is the size of the knapsack. Why is the size of the input related logarithmically to $W$?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Problems don't have runtimes. Furthermore, "pseudopolynomial" is the buzzword you want to search for. $\endgroup$– Raphael ♦Oct 28, 2014 at 19:25
-
$\begingroup$ See also here, here and here (duplicate?). $\endgroup$– Raphael ♦Oct 29, 2014 at 6:29
-
1$\begingroup$ Oh, and some nitpick: "doesn't violate its classification as NP" is an empty statement. Even if the algorithm ran in polynomial time, Knapsack would still be in NP and NP-complete. $\endgroup$– Raphael ♦Oct 29, 2014 at 6:33
-
$\begingroup$ If your knapsack has a size of say 6,345,987 that's seven digits. The size of the knapsack is over 6 million, the size of the problem is just seven digits. $\endgroup$– gnasher729Oct 19, 2019 at 15:46
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
Polynomial time means that the running time is bounded by a polynomial in the length of the input. The running time here is bounded by $nW$. $n$, the number of items, is surely less than the length of the input, so that part is fine. But $W$, the target weight, is a number that appears in the input, in binary. In $\ell$ bits, you can write a number up to $2^\ell$ so $W$ is potentially exponential in the length of the input, not polynomial.
answered Oct 29, 2014 at 9:24
$\begingroup$
$\endgroup$
4
Because you normally would not encode the sizes unary. Note that the number "100" would need 100 bit to encode unary (as opposed to the normal 7 bit), so the size of your Knapsack problem would be gigantic, and relative to the then-gigantic size the runtime would not be that bad.
-
$\begingroup$ Doesn't what you're saying suggest it is $P$? $\endgroup$– user8722Oct 28, 2014 at 19:14
-
$\begingroup$ Well yes. If you encode the input unary, then it's even in Logspace. But that's just a foul trick; consider for example a knapsack problem for $n=10^{12}$. You would need a terabyte to encode the problem unary! Unary encoding means that you encode the number by a sequence of $1$s. And relative to that GIGANTIC input size the runtime is polynomial. $\endgroup$– john_leoOct 28, 2014 at 19:19
-
3$\begingroup$ Just remember: If I increase your problem size exponentially, then of course you will be able to solve it in polynomial time, relative to the exponentially increased input size. $\endgroup$– john_leoOct 28, 2014 at 19:23
-
2$\begingroup$ You might also want to look at Wikipedia's site on Stronly NP-Complete Problems. $\endgroup$– john_leoOct 28, 2014 at 19:30
$\begingroup$
$\endgroup$
Knapsack is a weakly-NP Complete problem because when one encodes it in unary, it runs in polynomial time. However, this does not imply that P=NP it just means that you have artificially increased the input length and so it gives the illusion of running in polynomial time. Also, keep in mind that on small inputs the dynamic programming algorithm appears to be polynomial.
$\begingroup$
$\endgroup$
Think about it this way. Say you want to run the algorithm on an instance with $W=1,000,000$. When the program will ask you: ``Please input the value of $W$'', are you going to type 7 keys on your keyboard, or 1 million keys?
