13
$\begingroup$

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits).

For example testing whether a number $n$ is prime or not, requires a loop through numbers from 2 to $n-1$ and check if $n$ mod $i$ is zero or not. If the mod takes O(1) time, the overall time complexity will be O(n).

But if we let $x$ to be the number of required bits to write the input then $x = \log n$ (binary) so $n = 2^x$ and the running time of the problem will be O($2^x$) which is exponential.

My question is, if we consider the unary representation of input $n$, then always $x=n$ and then pseudo-polynomial time will be equal to polynomial time complexity. So why we never do this?

Furtheremore since there is a pseudo-polynomial time algorithm for knapsack, by taking $x=n$, the knapsack will be polynomial as a result P=NP

$\endgroup$
  • 3
    $\begingroup$ Actually, we do this, just not quite often. For the same reasons we don't usually deal with unary languages, but there are many interesting results related to these beasts. Have you looked into it? $\endgroup$ – André Souza Lemos Jan 6 '16 at 18:09
  • 2
    $\begingroup$ Yes, if you take away the difference between size and magnitude, you lose all concepts that are predicated on that difference. $\endgroup$ – André Souza Lemos Jan 6 '16 at 18:20
  • 7
    $\begingroup$ Because it's putting the demon into a nice dress. It does not make anything faster, it only makes the "running time complexity" meaningless. $\endgroup$ – Raphael Jan 6 '16 at 18:57
  • 4
    $\begingroup$ @Drupalist The unary knapsack problem is actually not known to be NP-complete because the normal reduction to the knapsack problem assumes that numbers are written out in binary. If you try doing the standard reduction but write the numbers in unary, the reduction can't be computed in polynomial time. As a result, the unary knapsack problem being solvable in polynomial time would not mean that P = NP. $\endgroup$ – templatetypedef Jan 6 '16 at 19:49
  • 2
    $\begingroup$ You may want to check out other answers tagged pseudo-polynomial, in particular this one. $\endgroup$ – Raphael Jan 7 '16 at 6:46
17
$\begingroup$

What this means is that unary knapsack is in P. It does not mean that knapsack (with binary-encoded numbers) is in P.

Knapsack is known to be NP-complete. If you showed that knapsack is in P, that would show that P = NP.

But you haven't shown that knapsack is in P. You've shown that unary knapsack is in P. However, unary knapsack is not known to be NP-complete (indeed, the standard suspicion is that it's most likely not NP-complete). Therefore, putting unary knapsack in P does not imply that P = NP.


So which problem should we care more about, knapsack or unary knapsack? If your motivation is based upon practical concerns, then the answer will depend on the size of the numbers you want to solve the knapsack problem for: if they're large, then you certainly care more about knapsack than unary knapsack. If your motivation is based upon theoretical concerns, then knapsack is arguably more interesting, because it allows us to get a deeper understanding -- it allows us to make the distinction between size vs magnitude -- whereas unary knapsack prevents us from making that distinction.


To answer the follow-up question about the dynamic programming algorithm for the knapsack problem:

Yes, he same dynamic programming algorithm can be applied to both knapsack and to unary knapsack. Its running time is polynomial in the magnitude of the numbers, but exponential (not polynomial) in the length of the numbers when encoded in binary. Thus, its running time is polynomial in the length of the input when the input is encoded in unary, but is not polynomial in the length of the input when the input is encoded in binary. That's why we do consider this dynamic programming algorithm to be a polynomial-time algorithm for unary knapsack, but don't consider it to be a polynomial-time algorithm for (binary-encoded) knapsack.

Recall that we say an algorithm runs in polynomial time if its running time is at most some polynomial of the length of the input, in bits.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much, I didn't know that the complexity class of unary and non-unary of the same algorithm may be different. Why the dynamic programming solution of standard knapsack can not be applied to unary knapsack, and it leaded to different class of complexity? I am having problem with understanding the unary version of problems. $\endgroup$ – M a m a D Jan 6 '16 at 20:21
  • $\begingroup$ @Drupalist, I've edited my answer to add two paragraphs at the end to answer that question. $\endgroup$ – D.W. Jan 6 '16 at 21:20
  • $\begingroup$ Thank you very much, from what I understand the difference between the input size and its magnitude is the reason of distinction between polynomial and pseudo-polynomial, by using unary representation I tried to eliminate this difference, If we forget knapsack and back to the numeric algorithms, I would like to know by setting $x=n$ what will be the interpretation of polynomial and pseudo-polynomial? Thanks again $\endgroup$ – M a m a D Jan 7 '16 at 23:17
  • $\begingroup$ @Drupalist, I'm not entirely sure what you mean by setting $x=n$, so I'm not sure how to answer. At this point I would suggest it might be best to ask a new (self-contained) question (and define all your variables in that question). This platform isn't so good for follow-up questions or back-and-forths: the best way we have to handle it is to ask a new question, based on what you've learned from the answers to this question. $\endgroup$ – D.W. Jan 8 '16 at 0:22
  • $\begingroup$ nice, but the last part is not correct. computational complexity does not assume a specific representation (whether one would like to call this bits or triads or whatever). However it indeed does depend on choice of representation (this is in a sense reflected in the relativisation-based proofs which can derive any result i.e both $P=NP$ and $P <> NP$) There is no definition of computational complexity that is only based on bits, in other words $\endgroup$ – Nikos M. Jan 13 '16 at 22:48
6
$\begingroup$

I would add one small thing to D.W.'s answer:

I have seen people who think that because unary Knapsack is in P therefore we can use it in place of Knapsack which best current algorithms have exponential time.

Let the input be $W=\{w_1, \ldots, w_n\}$ and $k$ and consider the dynamic programming algorithm for Knapsack and unary Knapsack. The running time for both of them are $O(nk)$. It is the same running time. I.e. if you have an input it will not matter if you use the dynamic programming for unary Knapsack or dynamic programming for Knapsack. Both of them will take (roughly) the same amount of time to solve the problem instance. Theoretically anywhere you use one you can use the other as well. You just need to convert numbers from unary to binary and vice versa.

So what is the point of defining complexity of algorithms w.r.t. to the size of the inputs? Why not always state them in terms of the parameters as $O(nk)$?

If you care about a problem in isolation you can do so. Actually that is what people in algorithms often do. The complexity of graph algorithms are often express in terms of the number vertices and the number of edges, not the size of the string that codes them.

But this is only when we are dealing with an isolated problem. It is not useful when we are dealing with problems with different kinds of inputs. For graphs we can talk about running time w.r.t. to number of vertices and edges. For Knapsack we can talk about the number of items and the size of the Knapsack. But what if we want to talk about both? E.g. when we want to reductions between problems, or discuss class of problems which includes arbitrary problems, not just those with a graph as input. We need a universal parameter of inputs. An input in general is just a string, it is us who interpret its symbols as unary numbers, binary numbers, graphs, etc. To develop a general theory of complexity of algorithm and problems we need a general parameter of inputs. The size of the input is an obvious choice and it turns out to be robust enough that we can build a reasonable theory on top of it. It is not the only possibility. For an artificial one we can build a theory based on $2$ to the size of the input. It will work fine.

Now we decide to use size as our universal parameter of inputs it enforces us to think about the encoding of objects in terms of strings. There are various way to encode them and they can different sizes. (They also make different things easy/hard.) In terms of a general theory of algorithms, whether we encode the input number in unary or binary becomes important. If we are using unary and the size of $k$ is $100$ the largest number we will get is $100$. If we are using binary $k$ can be as large as $2^{100}-1$. So when we are talking about the running time of solving Knapsack problems where the size of $k$ is 100 we get two very different situation: In one case we care about only inputs where $k$ is at most 100. In the other we care about inputs that can be as large as $2^{100}-1$.

Let's say I want to see if I can reduce SAT to Knapsack in polynomial time. Let's say the input formula for SAT has size $n$. Then I will be able to build only an input for Knapsack which has size polynomial in $n$. Let's say $p(n)$ is the size of the input for Knapsack that I build. If I use unary I can only put $k$ to be at most $p(n)$. If I use binary I can put $k$ to be as large as $2^{p(n)}-1$. It turns out I need to put $k$ quite large to be able to reduce SAT to Knapsack. So unary Knapsack will not work for reducing SAT to it. Binary Knapsack would however work. We will be able to create a Knapsack instance with much larger $k$ if we use binary.

Another way to think about this: Assume that you have a black box that solves unary Knapsack and another one which solves Knapsack. Assume that you have time to write an $n$ bit input for the black box. Which one of the black boxes is more powerful? Obviously the one which uses binary encoding. We can use it to solve Knapsack problems which have exponentially larger $k$ compare to problems that the unary Knapsack black box can solve.

$\endgroup$
  • $\begingroup$ Thank you very much, one more question, by converting the input to its unary representation what will happen to the problem of determining if a number is prime or not? This problem is polynomial based on the input magnitude but exponential based on input bits(as I pointed out in the question), will this convertion make anything better? $\endgroup$ – M a m a D Jan 7 '16 at 23:09
  • $\begingroup$ @Drupalist, say we are using the simple algorithm that goes over the numbers less than $n$ till it finds a factor. Its running time is $O(n)$ independent of whether you encode $n$ as unary or as binary. If you have a 1024 bit number like $b = 2^{1024}-1$, the algorithm is going to take (roughly) $2^{1024}-1$ independent of whether you give $2^{1024}-1$ as unary or as binary. For a particular input that you want to run your algorithm on it doesn't change much if you give it as unary or as binary. $\endgroup$ – Kaveh Jan 7 '16 at 23:43
  • $\begingroup$ nice clarification, however take a look at my comment under D.W's answer which is related to this post $\endgroup$ – Nikos M. Jan 13 '16 at 22:51

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.