Can strong NP-hardness really be shown using plain polytime reductions?

Question

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

Answer 1

According to the terminology in the paper by Garey and Johnson, polynomial-time transformations are not necessarily pseudo-polynomial transformations because it may violate item (d) in Definition 4.

Answer 2

To expand on Tsuyoshi's answer:

In the context of Garey and Johnson, consider a transformation from PARTITION (p. 47, Sec. 3.1) to MULTIPROCESSOR SCHEDULING (p. 65, Sec. 3.2.1, Item (7)).

The transformation (by restriction) involves setting $D=\frac{1}{2}\sum_{a\in A}l(a)$. But if the lengths of the tasks, the $l(a)$, are too large, then it cannot be the case that there exists a two-variable polynomial $q_2$ such that, $\forall I \in D_{\Pi}$, Max`$[f(I)] \le q_2$(Max$[I],$ Length$[I])$ (i.e. item (d) in the definition of a pseudo-polynomial transformation).

For instance, just consider an instance of MULTIPROCESSOR SCHEDULING where the value of all of the $l(a)$ are exponential in the number of the $l(a)$ (i.e. $|A|$). You're still manipulating the same number of "combinatorial objects" (so to speak), but they're all extremely large. Hence, NP-complete, but not strongly NP-complete.

You might want to read Wikipedia on a related topic. For instance, we have a dynamic programming-based polynomial-time algorithm for the NP-complete KNAPSACK problem -- at least, as long as the numbers are small enough. When the numbers get too big, this "polynomial-time" algorithm will display "exponential behavior." (G&J, p. 91, Sec 4.2)