What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input value; so how do we explain this shift from exponential to polynomial?
2 Answers
As it is stated in "Computers and Intractability: a Guide to the Theory of NP-Completeness" A pseudo-polynomial-time algorithm will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, which might be rare for the applications we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.”
You can consider knapsack as a good example of weakly-Np Complete problem. In this case the complexity of the dynamic programming solution is $O(nW)$ which is well in most practical cases.
It is known that there is no pseudo-polynomial time algorithm for Strong NP-Complete problems (like Steiner Tree) unless P=NP.
-
$\begingroup$ Does this mean that pseudopolynomial algorithms work for problems that take numerical inputs (as implied from your answer)? $\endgroup$– mrkFeb 14, 2013 at 19:09
-
$\begingroup$ @saadtaame: Yes, the key point is that they are numerical problems in which the running time is related to the numerical input data. $\endgroup$– RezaFeb 14, 2013 at 21:40
This answer pertains to quasipolynomial algorithms rather than pseudopolynomial ones.
A quasipolynomial algorithm tells us that the problem is probably not NP-hard. The (somewhat) commonly-believed Exponential Time Hypothesis (ETH) states that 3SAT on $n$ variables requires time $2^{\Omega(n)}$. Since 3SAT is in NP, the ETH implies that any NP-complete problem requires time $2^{n^{\Omega(1)}}$, which grows faster than quasipolynomial (assuming by the latter is meant $2^{\log^{O(1)} n}$).
-
$\begingroup$ But there are plenty of NP-hard problems with pseudo-polynomial algorithms. $\endgroup$– RaphaelFeb 12, 2013 at 6:29
-
-
1$\begingroup$ pseudo-polynomial is not assuming: $2^{\log^{O(1)} n}$ it has very clear definition. Also I didn't see such an assumption anywhere, whould you provide any reference? Also Raphael is right, for all problems which are belong to weakly np-compelete (means they are also np-hard) there is pseudo polynomial time algorithm. $\endgroup$– user742Feb 12, 2013 at 9:40
-
$\begingroup$ Pseudo-polynomial means different things to different people. As to the exponential time hypothesis, google has quite a file on it. $\endgroup$ Feb 12, 2013 at 16:26
-
1$\begingroup$ No, actually $2^{O(\log n)} = n^{O(1)}$, $2^{\log^{O(1)} n}$ is quasipolynomial (ah - that's the correct term!). The complexity class $2^{n^{O(1)}}$ is usually called subexponential. $\endgroup$ Feb 12, 2013 at 22:17