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?

  • $\begingroup$ What do you mean by "improves"? Relative to what? $\endgroup$ – Raphael Feb 12 '13 at 6:29
  • $\begingroup$ @Raphael Where does the polynomial part come from? $\endgroup$ – saadtaame Feb 12 '13 at 13:41

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$ – saadtaame Feb 14 '13 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$ – Reza Feb 14 '13 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$ – Raphael Feb 12 '13 at 6:29
  • $\begingroup$ Can you give an example? $\endgroup$ – Yuval Filmus Feb 12 '13 at 6:50
  • 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$ – user742 Feb 12 '13 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$ – Yuval Filmus Feb 12 '13 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$ – Yuval Filmus Feb 12 '13 at 22:17

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.