¿Se puede mostrar realmente una fuerte dureza NP usando reducciones simples de polytime?

Recientemente leí una prueba que tenía la intención de mostrar que un problema era fuertemente NP-duro, simplemente reduciéndolo (en tiempo polinómico) a partir de un problema fuertemente NP-duro. Esto no tenía ningún sentido para mí. Pensé que tendrías que demostrar que cualquier número utilizado en la reducción y las instancias del problema que estás reduciendo están polinómicamente limitadas en el tamaño del problema.

Luego vi que Wikipedia daba las mismas instrucciones generales para este tipo de prueba, pero no estaba realmente convencido hasta que vi a Garey & Johnson decir básicamente lo mismo. Para ser específicos, dicen: "Si es NP-duro en el sentido fuerte y existe una transformación pseudo-polinomial de a , entonces es NP-duro en el sentido fuerte", y "Tenga en cuenta que, por definición, un algoritmo de tiempo polinomial es también un algoritmo de tiempo pseudo-polinomial".$\Pi$$\Pi$$\Pi'$$\Pi'$

Por supuesto, tomo la palabra de Garey & Johnson sobre esto: simplemente no entiendo cómo puede ser correcto, que es en lo que me gustaría un poco de ayuda. Aquí está mi razonamiento (presumiblemente defectuoso) ...

Hay problemas fuertemente NP-completos, y todos estos son (por definición) fuertemente NP-hard y NP-complete. Todo problema NP-completo puede (por definición) reducirse a cualquier otro en tiempo polinomial (y por lo tanto pseudopolinomial). Dadas las declaraciones de Garey & Johnson, por lo tanto, me parece que cada problema NP-completo es fuertemente NP-complete, y, por lo tanto, cada problema NP-hard es fuertemente NP-hard. Esto, por supuesto, hace que el concepto de fuerte dureza NP no tenga sentido ... ¿qué me estoy perdiendo?

Editar / actualizar (basado en la respuesta de Tsuyoshi Ito):

El requisito (d) de la definición de Garey & Johnson de una transformación (pseudo) polinomial (el tipo de reducción necesaria para conferir dureza NP en el sentido fuerte) es que la magnitud numérica más grande en la instancia resultante esté limitada polinomialmente, como una función del tamaño del problema y la magnitud numérica máxima del original. Esto, por supuesto, significa que si el problema original es NP-duro en el sentido fuerte (es decir, incluso cuando sus magnitudes numéricas están limitadas polinómicamente en el tamaño del problema), esto también será cierto para el problema al que se reduce. Este no sería necesariamente el caso para una reducción de polytime ordinaria (es decir, una sin este requisito adicional).

Según la terminología en el artículo de Garey y Johnson, las transformaciones de tiempo polinomial no son necesariamente transformaciones pseudo-polinomiales porque pueden violar el ítem (d) en la Definición 4.

Para ampliar la respuesta de Tsuyoshi:

En el contexto de Garey y Johnson, considere una transformación de PARTICIÓN (p. 47, Sec. 3.1) a PROGRAMACIÓN MULTIPROCESADOR (p. 65, Sec. 3.2.1, Artículo (7)).

$D=\frac{1}{2}\sum_{a\in A}l(a)$$l(a)$$q_2$$\forall I \in D_{\Pi}$$[f(I)] \le q_2$$[I],$$[I])$ (es decir, el ítem (d) en la definición de una transformación pseudo-polinomial).

$l(a)$$l(a)$$|A|$

Es posible que desee leer Wikipedia sobre un tema relacionado . Por ejemplo, tenemos un algoritmo de tiempo polinómico basado en programación dinámica para el problema KNAPSACK NP-completo, al menos, siempre que los números sean lo suficientemente pequeños. Cuando los números se vuelven demasiado grandes, este algoritmo de "tiempo polinómico" mostrará "comportamiento exponencial". (G&J, p. 91, sección 4.2)