Pseudo-polynomial time algorithm for NP-Complete Problems

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?

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.

StackExchange Computer Science Q#39753, answer score: 5