4
$\begingroup$

In a different post it came up that (using the Turing machine model of computation), it is not even safe to say that $N$ numbers can be read in $O(N)$ time. To me this is boggling since it's something I take for granted in the RAM model of computation, and I admittedly only have a cursory understanding of Turing machines.

However, the more boggling part is that the same person claimed that in the Turing machine model we cannot read $N$ numbers even in exponential time, BUT that we can read the input for Knapsack and fill a table of size $N$ by $w$ in exponential time.

How can filling a two-dimensional $N$ by $w$ array take less time than an $N$ by $1$ array?

$\endgroup$
  • 1
    $\begingroup$ I slightly edited your question to make it, I hope that I haven't changed it too much. Feel free to roll back or edit. $\endgroup$ – Kaveh Jun 30 '13 at 7:08
  • $\begingroup$ May be your problem is with RAM model, I'd suggest to read this question and the accepted answer: cs.stackexchange.com/questions/1643/… $\endgroup$ – user742 Jul 1 '13 at 12:23
8
$\begingroup$

The complexity of an algorithm is defined in the size of input. You can talk about the running time of algorithm in other parameters but the classic complexity classes like $\mathsf{P}$ and $\mathsf{NP}$ are defined in the size of input (in Turing machine model).

For an algorithm to read $N$ numbers in $O(N)$ time it needs to be able to read a number in constant time. This might seem OK at first but it is not. The time that it takes to read a number depends on the number of bits needed to store it. If you want to read a number which has $2$ bits and a number which has $2^{100}$ bits to see even on an actual computer it really depends on the number of bits.

This confusion about reading a number in constant time comes because in programming languages the data types for numbers has a maximum number of bits. For example, in many programming languages an integer variable cannot store a number more than 64 bits. So it always reads 64 bits and therefore seems constant time. But if you don't have an upper bound on the size of numbers that you might read it can take arbitrary large amount of time.

Therefore we cannot bound the running time of an algorithm reading $N$ numbers simply in $N$, it depends on how large those numbers are.

OK, so does this mean we shouldn't use the RAM model based analysis for algorithms since it hides these issues? Well, we can use them, and it is usually much easier to use them. But one should be careful about these issues. That is the reason we put emphasis on what is the size of the input for a problem when teaching data structures and algorithms.

But it is not just the input. Take for example the following program:

Input: n
x = 2
for i from 0 to n
  x = x*x
return x

At first glance this looks like to be a polynomial time algorithm. We have a loop that is executed $n$ times and inside the loop we perform a single simple multiplication. So this is polynomial time?

No, it is not. The size of input is $\lg n$ (the number of bits used to give $n$) so this the loop is executed exponentially many times. But that is not the only problem. Let's look at

Input: n
x = 2
for i from 0 to log n
  x = x*x
return x

Is this one polynomial time?

It is not. Although the loop is executed only a linear number of times in the input length the number $x$ grows and it grows it takes more time to multiply it. To see this ask we can look at the number of bits $x$ the algorithm returns. Surely an algorithm running in polynomial time cannot return exponentially many bits, right?

$$ (0,2)\\ (1,4)\\ (2,16)\\ (3,256) .\\ .\\ .\\ (i, 2^{2^{i}}) $$

So the output is $2^{2^{\lg n}}$ which has $2^{\lg n}$ bits, exponentially more than the number of bits in input.

Now why this algorithm is not polynomial time? Well, multiplying two numbers is not constant time, and as $x$ grows the multiplication will take longer and longer time, and the amount of time it takes to multiply two numbers grows with the number of bits they have.

In a language like C you will quickly overflow if you define $x$ to be of the standard data types for storing integers.

OK, so why people use the RAM model for algorithms analysis then? Because it is much easier to analyze algorithms in the RAM model and if one is careful the result is correct. for example, if you only use operations which are polynomial time in the size of their input (like multiplication) and during the execution you only store and use objects which are of polynomial size in the size of input then if your algorithm executes a polynomially many operations then your algorithm is actually polynomial time.

Now, returning to the dynamic programming algorithm for the Knapsack problem. The space complexity of the algorithm is roughly $w^2n$ and the number of operations executed by the algorithm is $wn$. The size of input is something between $n+\lg w$ and $n\lg w + \lg w$ since we can assume all numbers are at most $w$ (otherwise we can ignore them). The exact size of input depends on the size of the numbers given to use. So it is not going to be polynomial time in general.

However, when $w$ is exponentially small relative to $n$, i.e. $w \approx \lg n$ the size of input becomes roughly something between $2n$ and $n^2$ and the running time becomes roughly $n^2$. In this case the running time is going to be bounded by a polynomial in the size of input.

When $w \approx \lg n$, it means that the numbers are so small that you can encode them in unary in place of binary with a at most polynomial increase in the size. This is why people sometimes say that Knapsack is polynomial time when the input numbers are encoded in unary. That is essentially the same as saying $w \approx \lg n$.

Note that if we encoded the numbers in the input in unary, the size of input would be between $n+w$ and $nw+w$ and then the algorithm is polynomial time in the size of the input.

In short, dynamic programming for Knapsack is polynomial time when the number $w$ is at most a polynomial in the total length of the input. This can be phrased in different ways but that is what essentially pseudo-polynomial means.

I think these confusion happen partly because people forget to emphasis the encoding used for input and output and without fixing those encodings the computational problem is not completely defined. All objects whether numbers, graphs, strings, etc. should be encoded with the basic objects that the machine deals with, which is usually bits. And there are many different ways of encoding other objects with bits, this is particularly important in practice when dealing with graphs. Some graph problems can be solved faster using adjacency matrix, other graph problems can be solved faster using adjacency lists, etc. and until the encodings are not fixed the complexity of the graph problem is not well defined.

$\endgroup$
  • $\begingroup$ Thank you, I think I do understand a lot of what you're saying. I'm still confused though that even in textbooks/articles that seem to use the RAM model for all other algorithms, they call Knapsack DP solution "pseudo-polynomial" which makes me think they are saying that in a RAM sense. And if that is the case, I think their basis for saying that has more to do with the relative values of w vs N than the finite length encoding issue you discuss here. Indeed, it would seem that no infinite problem is boundable when we consider finite length encoding as you do... or am I wrong there too? $\endgroup$ – The111 Jun 30 '13 at 6:30
  • $\begingroup$ @The111, usually in data structures and algorithm textbooks we deal with algorithms that never store objects which are too large (like the one I used in my example) so things turn out to be OK. Introducing Turing machines would take too much time and doesn't seem necessary unless we want to talk about the complexity of problems. For algorithms, it is usually enough to state the complexity in terms of parameters like the number of vertices and the number of edges for a given graph. $\endgroup$ – Kaveh Jun 30 '13 at 7:10
  • $\begingroup$ We do sometimes assume some operations are constant time (like multiplication) while in practice they are not, but it normally adds only a logarithmic factor to the run time. We can also be more careful about them if we want and charge them a more realistic amount of time (e.g. quadratic in the size of their inputs) in place of constant time. But when we want to talk about the complexity of problems (not algorithms) then we have to be more careful and that is the reason complexity theory textbooks first introduce the Turing machine model before discussing complexity. $\endgroup$ – Kaveh Jun 30 '13 at 7:15
  • $\begingroup$ Knapsack is NP-complete with no if (when using the normal encoding of the problem which uses binary numbers). However, we also see that in practice it is sometimes possible to solve Knapsack. I think the concept of pseudo-polynomial is introduced to explain this observed phenomenon. Btw, there is a huge area of research called parameterized complexity which you might find interesting. $\endgroup$ – Kaveh Jun 30 '13 at 7:16
  • $\begingroup$ @Kaveh What about other problems like weighted interval scheduling: Given jobs 1,..,n, starting times s(1),..,s(n), finishing times f(1),..,f(n) and values v(1),..,v(n). The goal is to find a maximum value subset of mutually compatible jobs, where two jobs i,j are called compatible iff they don't overlap, i.e. [s(i),f(i)) and [s(j),f(j)) are disjoint. We can solve this problem with dynamic programming in O(n), if we assume the jobs are presorted by earliest finish time, i.e. f(1) <= .. <= f(n). Where's the difference to knapsack? Why this is not pseudo-polynomial? $\endgroup$ – 0xbadf00d Sep 4 '14 at 11:46

Your Answer

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

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