4
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ Problems don't have runtimes. Furthermore, "pseudopolynomial" is the buzzword you want to search for. $\endgroup$ – Raphael Oct 28 '14 at 19:25
  • $\begingroup$ See also here, here and here (duplicate?). $\endgroup$ – Raphael Oct 29 '14 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 '14 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$ – gnasher729 2 days ago
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Doesn't what you're saying suggest it is $P$? $\endgroup$ – user8722 Oct 28 '14 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_leo Oct 28 '14 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_leo Oct 28 '14 at 19:23
  • 2
    $\begingroup$ You might also want to look at Wikipedia's site on Stronly NP-Complete Problems. $\endgroup$ – john_leo Oct 28 '14 at 19:30
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy