I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I would have thought that you’d have to show that any numbers used in the reduction and the instances of the problem you’re reducing to were polynomially bounded in the problem size.
I then saw that Wikipedia gave the same general instructions for this sort of proof, but I wasn’t really convinced until I saw Garey & Johnson say basically the same thing. To be specific, they say, “If $\Pi$ is NP-hard in the strong sense and there exists a pseudo-polynomial transformation from $\Pi$ to $\Pi'$, then $\Pi'$ is NP-hard in the strong sense,” and “Note that, by definition, a polynomial time algorithm is also a pseudo-polynomial time algorithm."
Of course, I take the word of Garey & Johnson on this—I just don’t understand how it can be correct, which is what I’d like some help with. Here’s my (presumably flawed) reasoning…
There are strongly NP-complete problems, and all these are (by definition) strongly NP-hard as well as NP-complete. Every NP-complete problem can (by definition) be reduced to any other in polynomial (and therefore pseudopolynomial) time. Given the statements of Garey & Johnson, it would therefore seem to me that every NP-complete problem is strongly NP-complete, and, therefore, that every NP-hard problem is strongly NP-hard. This, of course, makes the concept of strong NP-hardness meaningless … so what am I missing?
Edit/update (based on Tsuyoshi Ito’s answer):
The requirement (d) from Garey & Johnson’s definition of a (pseudo)polynomial transformation (the kind of reduction needed to confer NP-hardness in the strong sense) is that the largest numerical magnitude in the resulting instance be polynomially bounded, as a function of the problem size and maximal numerical magnitude of the original. This, of course, means that if the original problem is NP-hard in the strong sense (that is, even when its numerical magnitudes are polynomially bounded in the problem size), this will also be true of the problem you reduce to. This would not necessarily be the case for an ordinary polytime reduction (that is, one without this extra requirement).