# 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. Dec 5, 2016 at 13:16
• 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. Dec 5, 2016 at 20:51