Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
What do you mean by "improves"? Relative to what? –  Raphael Feb 12 '13 at 6:29
    
@Raphael Where does the polynomial part come from? –  saadtaame Feb 12 '13 at 13:41
add comment

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.

share|improve this answer
    
Does this mean that pseudopolynomial algorithms work for problems that take numerical inputs (as implied from your answer)? –  saadtaame Feb 14 '13 at 19:09
    
@saadtaame: Yes, the key point is that they are numerical problems in which the running time is related to the numerical input data. –  Reza Feb 14 '13 at 21:40
add comment

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}$).

share|improve this answer
    
But there are plenty of NP-hard problems with pseudo-polynomial algorithms. –  Raphael Feb 12 '13 at 6:29
    
Can you give an example? –  Yuval Filmus Feb 12 '13 at 6:50
1  
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. –  user742 Feb 12 '13 at 9:40
    
Pseudo-polynomial means different things to different people. As to the exponential time hypothesis, google has quite a file on it. –  Yuval Filmus Feb 12 '13 at 16:26
1  
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. –  Yuval Filmus Feb 12 '13 at 22:17
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.