patternMinor
Do I understand pseudo polynomial time correctly?
Viewed 0 times
polynomialtimeunderstandpseudocorrectly
Problem
The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time correctly.
My current understanding is that pseudo polynomial time means polynomial in the magnitude of the input, and polynomial time is polynomial in the number of bits it takes to represent the input. Thus, looking through each element of an array is $O(n)$ in the magnitude of its length (pseudo-polynomial), but it is exponential in the number of bits in the length of the array. In the same way, binary search is $O(log_2 n)$ in the magnitude of the length of $n$, but is linear in the number of bits in $n$ making it "pseudo-logarithmic".
If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?
My current understanding is that pseudo polynomial time means polynomial in the magnitude of the input, and polynomial time is polynomial in the number of bits it takes to represent the input. Thus, looking through each element of an array is $O(n)$ in the magnitude of its length (pseudo-polynomial), but it is exponential in the number of bits in the length of the array. In the same way, binary search is $O(log_2 n)$ in the magnitude of the length of $n$, but is linear in the number of bits in $n$ making it "pseudo-logarithmic".
If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?
Solution
The running time for binary search that you quote applies for the so-called RAM model. I think that it is usually assumed that the machine words have size $\Theta(\log n)$ bits, where $n$ is some natural parameter like the length of the input.
For binary search, the input has size $\Theta(n)$, assuming that the array's datatype fits in a constant number of machine words, and so the running time $O(\log n)$ is logarithmic in the input size. The running time of the dynamic programming algorithm for knapsack is $\Theta(nW)$, but the size of the input is $O(n\log W)$ (in fact somewhat less, since machine words have superconstant size). This is not polynomial in the size of the input. However, if the weights are encoded in unary, then the size of the input is $O(nW)$ (again, actually somewhat less), and so the algorithm is pseudo-polynomial. It's a matter of encoding - whether you encode the weights in binary or in unary.
For binary search, the input has size $\Theta(n)$, assuming that the array's datatype fits in a constant number of machine words, and so the running time $O(\log n)$ is logarithmic in the input size. The running time of the dynamic programming algorithm for knapsack is $\Theta(nW)$, but the size of the input is $O(n\log W)$ (in fact somewhat less, since machine words have superconstant size). This is not polynomial in the size of the input. However, if the weights are encoded in unary, then the size of the input is $O(nW)$ (again, actually somewhat less), and so the algorithm is pseudo-polynomial. It's a matter of encoding - whether you encode the weights in binary or in unary.
Context
StackExchange Computer Science Q#13104, answer score: 4
Revisions (0)
No revisions yet.