[Solved]: Why not to take the unary representation of numbers in numeric algorithms?

Problem Detail: 

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

Asked By : Drupalist

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51542