# Validity of exponentiation in a polynomial time reduction

I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.

In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-completeness results of path computation under several additive/multiplicative constraints. The first problem is the following :

Given a directed graph $G=(V,A)$ and two weight metrics $w_1$ and $w_2$ over the edges, define, for a path $P$, $w_i(P)=\sum_{a\in P}w_i(a)$ ($i=1,2$). Given two nodes $s$ and $t$, the problem is to find a path $P$ from $s$ to $t$ s.t. $w_i(P)\leq W_i$, where the $W_i$ are given positive numbers (example: Delay constraint and cost in a network).

The authors prove that this problem is $\mathsf{NP}$-complete by providing a polynomial reduction from PARTITION.

Then they present the same problem except that the metrics are multiplicative, i.e., $w'_i(P)=\prod_{a\in P}w'_i(a)$. In order to prove the multiplicative version is $\mathsf{NP}$-complete, they provide a "polynomial" reduction from the additive version just by putting $w'_i(a)=e^{w_i(a)}$ and $W'_i=e^{W_i}$.

I am very puzzled by this reduction. Since $W'_i$ and $w'_i(a)$ are part of the input (in binary, I guess), then the $|w'_i(a)|$ and $|W'_i|$ are not polynomial in $|w_i(a)|$ and $|W_i|$. Thus the reduction is not polynomial.

Am I missing something trivial or is there a flaw in the proof? My doubt is about the validity of the proof, even if the result is clearly true.

Paper reference : Zheng Wang, Jon Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications. IEEE Journal on Selected Areas in Communications 14(7): 1228-1234 (1996).

• I've checked the paper, this is surely a flaw in their proof. – domotorp Dec 5 '16 at 13:16
• The paper is cited more than 2000 times. This is scary... – Lamine Dec 5 '16 at 15:13
• Well, probably most citations don't use this particular result, and also, after all, it is still true. I was told examples when they had to withdraw several papers building on a false result. Also, this exponentiation trick is so standard that probably most people don't even think it through and realize what you did, that the length of the input changes. – domotorp Dec 5 '16 at 20:51