<p>To expand on Tsuyoshi's answer:</p>

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

<p>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 <em>too large</em>, 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).</p>

<p>For instance, just consider an instance of MULTIPROCESSOR SCHEDULING where the <em>value</em> of all of the $l(a)$ are exponential in the <em>number</em> 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.</p>

<p>You might want to read <a href="http://en.wikipedia.org/wiki/Weakly_NP-complete">Wikipedia on a related topic</a>. 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&amp;J, p. 91, Sec 4.2)</p>

CC BY-SA 3.0
2011-07-14T16:23:23.280Z
2011-07-14T16:23:23.280Z
Daniel Apon
<p>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.</p>

CC BY-SA 3.0
2011-07-14T16:32:20.513Z
Right—so a polynomial *algorithm* is necessarily pseudopolynomial, but a polynomial reduction isn't necessarily what G&J call a pseudopolynomial transformation. In fact, their item (d) is exactly what I thought was missing (i.e., some restriction on number size). Thanks.
Magnus Lie Hetland
CC BY-SA 3.0
2011-07-14T16:00:05.813Z
2011-07-14T16:00:05.813Z
Tsuyoshi Ito
<p>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.</p>

<p>I then saw that Wikipedia gave the <a href="http://en.wikipedia.org/wiki/Strongly_NP-complete">same general instructions</a> for this sort of proof, but I wasn’t really convinced until I saw <a href="http://portal.acm.org/citation.cfm?doid=322077.322090">Garey &amp; Johnson</a> 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&#39;$, then $\Pi&#39;$ is NP-hard in the strong sense,” and “Note that, by definition, a polynomial time algorithm is also a pseudo-polynomial time algorithm."</p>

<p>Of course, I take the word of Garey &amp; 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…</p>

<p>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 &amp; 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?</p>

<p><strong>Edit/update</strong> (based on Tsuyoshi Ito’s answer):</p>

<p>The requirement (d) from Garey &amp; 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 <em>not</em> necessarily be the case for an ordinary polytime reduction (that is, one without this extra requirement).</p>

CC BY-SA 3.0
2011-07-14T17:14:00.877Z
Great! My math TA did this yesterday and I though it fishy. Now I can give him a link.
Raphael
<cc.complexity-theory><np-hardness><reductions>
Can strong NP-hardness really be shown using plain polytime reductions?
Magnus Lie Hetland
# Can strong NP-hardness really be shown using plain polytime reductions?

(Asked by: username_0 on 2011-07-14)

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](http://en.wikipedia.org/wiki/Strongly_NP-complete) for this sort of proof, but I wasn’t really convinced until I saw [Garey & Johnson](http://portal.acm.org/citation.cfm?doid=322077.322090) 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 username_3’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).

**Tags:** cc.complexity-theory, np-hardness, reductions

> **Comments:**
> **username_1**: Great! My math TA did this yesterday and I though it fishy. Now I can give him a link.  

---

## 2 answers

### Answer by username_3 on 2011-07-14. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: Right—so a polynomial *algorithm* is necessarily pseudopolynomial, but a polynomial reduction isn't necessarily what G&J call a pseudopolynomial transformation. In fact, their item (d) is exactly what I thought was missing (i.e., some restriction on number size). Thanks.  

---

### Answer by username_2 on 2011-07-14. Score: 10

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](http://en.wikipedia.org/wiki/Weakly_NP-complete). 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)


---

