patternMinor
Weak and strong completeness
Viewed 0 times
andstrongcompletenessweak
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#9686, answer score: 6
Revisions (0)
No revisions yet.