15
$\begingroup$

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack.

Why is this not a polynomial-time algorithm?

I have read that one needs $\lg W$ bits to represent $W$, so it is exponential time. But, I don't understand, one also needs $\lg n$ bits to represent $n$, doesn't one? So, for example, merge sort is not polynomial time, because its complexity is $O(n\lg n)$ and one needs $\lg n$ to represent $n$?

What am I missing here?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
16
$\begingroup$

When we say polynomial or exponential, we mean polynomial or exponential in some variable.

$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the size of the input.

This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their weights), the input of the knapsack problem is $n$ numbers $\leq W$. Each number is represented with $\log W$ bits, and there are $n$ numbers, so the size of the instance is $n\log W$.

This makes $nW$ not polynomial in the size of the instance, since $W$ is exponential in $\log W$.

However, (coming back to your example about sorting) an instance for sorting consists of $n$ elements to be sorted, and representing these takes at least $n$ bits (and probably a bit more, since the elements themselves are probably bigger than $1$ bit each). We can represent the number $n$ using $\log n$ bits, but we can't represent $n$ things using $\log n$ bits.

The main difference is that $W$ represents a number in the input, while $n$ represents "the number of things".

Note that if we were to "cheat", we could represent $W$ using $W$ bits if we used a unary encoding. This version of the problem is technically polynomial, but really only because we were deliberately being less efficient.

It turns out that there is a whole class of Strongly NP-Hard Problems, which are still NP-hard even when the input is represented in unary format. But Knapsack is not one of these problems.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This question may be a duplicate. In case it gets closed as such, you may want to check if you want to repost your answer on that other question. $\endgroup$
    – Raphael ♦
    Feb 6, 2016 at 17:08
  • $\begingroup$ @Raphael Doh. I'll not repost my answer, since it's already covered by Tom's answer to the other question. (Well, and by his answer to this one, too, but I wanted to make what I think is the main point more succinctly.) $\endgroup$
    – David Richerby
    Feb 6, 2016 at 17:12
  • 1
    $\begingroup$ @DavidRicherby I think it's useful to gather multiple answers in the same place. More useful than letting them rot at some duplicate, for that matter. $\endgroup$
    – Raphael ♦
    Feb 6, 2016 at 17:15
  • $\begingroup$ Well, oops. I suppose I should have noticed that this is a duplicate... $\endgroup$
    – Tom van der Zanden
    Feb 6, 2016 at 17:15
3
$\begingroup$

I have read that one needs $\lg ⁡W$ to represent $W$ so it is exponential-time. But, I don't understand, also one needs $\lg ⁡n$ to represent $n$, no?

This is a great question. You need to look at what the input actually is. The input consists of $n$ items, each of which has a weight $w_i$ and value $v_i$, plus the capacity $W$ of your knapsack.

Each of the $w_i$w, the $v_i$s and $W$ is a number, written in binary. In particular, each $w_i$ and $v_i$ must be at least one bit, so the length of the input is at least $n$ bits (well, even $2n$ bits). You're absolutely correct that it takes $\log n$ bits to write $n$ in binary and $\log W$ bits to write $W$. But the point is that $n$ isn't written out in binary as part of the input.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think the points "is that $n$ isn't" just "written out in binary as part of the input", since the analysis would apply even if it was "written out in binary as part of the input". ​ ​ $\endgroup$
    – user12859
    Feb 6, 2016 at 17:52
  • $\begingroup$ So why isnt n written in binary ? $\endgroup$
    – DollarAkshay
    Apr 16, 2018 at 6:08
  • $\begingroup$ @AkshayLAradhya You don't write $n$ in the input at all. You just write a list of items, and $n$ is the number of items in that list. Writing $n$ as well (in binary or unary) wouldn't make any asymptotic difference to the length of the input. $\endgroup$
    – David Richerby
    Apr 16, 2018 at 7:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.