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

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top