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
4
$\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$
1
$\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

Your Answer

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