Validez de exponenciación en una reducción de tiempo polinomial

Hice esta pregunta hace 10 días en cs.stackexchange aquí, pero no tenía ninguna respuesta.

En un artículo muy famoso (en la comunidad de redes), Wang y Crowcroft presentan algunos resultados de -completitud del cálculo de ruta bajo varias restricciones aditivas / multiplicativas. El primer problema es el siguiente:$\mathsf{NP}$

Dado un gráfico dirigido y dos métricas de peso y sobre los bordes, defina, para una ruta , ( ) Dados dos nodos y , el problema es encontrar un camino de a st , donde el se dan números positivos (ejemplo: restricción de retardo y del coste en una red).w 1 w 2 P w i ( P ) = ∑ a ∈ P w i ( a ) i = 1 , 2 s t P s t w i ( P ) ≤ W i W $G=(V,A)$$w_1$$w_2$$P$$w_i(P)=\sum_{a\in P}w_i(a)$$i=1,2$$s$$t$$P$$s$$t$$w_i(P)\leq W_i$$W_i$

Los autores prueban que este problema es completo al proporcionar una reducción polinómica de PARTICIÓN.$\mathsf{NP}$

Luego presentan el mismo problema, excepto que las métricas son multiplicativas, es decir, . Para demostrar que la versión multiplicativa es N P -completa, proporcionan una reducción "polinomial" de la versión aditiva simplemente poniendo y .$w'_i(P)=\prod_{a\in P}w'_i(a)$$\mathsf{NP}$$w'_i(a)=e^{w_i(a)}$$W'_i=e^{W_i}$

Estoy muy perplejo por esta reducción. Como y son parte de la entrada (en binario, supongo), entoncesyno son polinomiales eny. Por lo tanto, la reducción no es polinómica.$W'_i$$w'_i(a)$$|w'_i(a)|$$|W'_i|$$|w_i(a)|$$|W_i|$

¿Me estoy perdiendo algo trivial o hay una falla en la prueba? Mi duda es sobre la validez de la prueba, incluso si el resultado es claramente cierto.

Referencia de papel: Zheng Wang, Jon Crowcroft. Enrutamiento de calidad de servicio para aplicaciones multimedia compatibles . IEEE Journal on Selected Areas in Communications 14 (7): 1228-1234 (1996).

La prueba presentada en el documento no es concluyente.

Sin embargo, el resultado indicado en sí mismo es correcto. Se puede derivar fácilmente cambiando ligeramente la reducción y usando SUBSET PRODUCT en lugar de SUBSET SUM.

Un enlace útil para el problema del PRODUCTO SUBSET:
/cs/7907/is-the-subset-product-problem-np-complete