5
$\begingroup$

For problems like Knapsack there is a pseudo-polynomial time algorithm and it is NP-complete. So we reduce every other problem in NP in polytime to Knapsack.

But why don't we have then a pseudo-polynomial time algorithm for all problems in NP?

$\endgroup$
4
$\begingroup$

An algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric values in the input. It doesn't make sense to talk about pseudo-polynomial time algorithms for all problems in $NP$ since many of them do not have numeric values in their input at all.

However, if you are looking at two problems for which the definition does apply (for instance 2-Partition (weakly $NP$-complete, has a pseudopolynomial time algorithm) and 3-Partition (strongly $NP$-complete, not believed to have a pseudopolynomial time algorithm) then how is it possible a polynomial reduction from 3-Partition to 2-Partition does not result in a pseudopolynomial algorithm for 3-Partition?

The answer is that a polynomial reduction may create very large numeric values. Every known reduction from 3-Partition to 2-Partition creates numbers that are exponentially bigger than the orignal numbers. Exponentially larger numbers only take polynomially more space to represent, so a polynomial reduction can very easily create exponential numeric values.

So even though we have a pseudopolynomial time algorithm (that runs in polynomial time in the numeric values of the input) for 2-Partition it does not work as a pseudopolynomial time algorithm for 3-Partition, because the reduction makes the numbers much larger, so the algorithm is no longer pseudopolynomial in the original numbers.

$\endgroup$

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.