Why not to take the unary representation of numbers in numeric algorithms?

Question

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

Answer 1

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, the same dynamic programming algorithm can be applied to both knapsacks and to the 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.

Answer 2

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.

Answer 3

In short and simple, I will show you why.

Suppose, you have a factorization algorithm. Except for the small difference that one accepts integers for input and the other $Tally$. As you can see both code snippets are similar.

x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Notice that the above algorithm is polynomial of the numeric value of $x$. It will take $x$ amount of steps in the loop. But when it comes to bit-size its actually $O(2^n)$.

Suppose, I make a small edit to the code that will take in $Tally/Unary$. It will now be $O(n)$ time in both value and length of the input $x$.

x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

The input representation does not make the code run faster. Even though the 2nd algorithm is truly poly-time. Its not very practical in finding the factors for RSA.