<p>The proof as presented in the paper is not conclusive.</p>

<p>However, the stated result itself is correct. It can easily be derived by slightly changing the reduction and by using SUBSET PRODUCT instead of SUBSET SUM.</p>

<p>A useful link for the SUBSET PRODUCT problem:<br>
<a href="https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete">https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete</a></p>

CC BY-SA 3.0
2016-12-05T13:19:08.723Z
2016-12-05T13:19:08.723Z
2017-04-13T12:48:30.830Z
Gamow
<p>I asked this question 10 days ago on cs.stackexchange <a href="https://cs.stackexchange.com/questions/66367/validity-of-exponentiation-in-a-polynomial-time-reduction">here</a> but I didn'y have any answer.</p>

<p>In a <a href="http://eecs.oregonstate.edu/~thinhq/teaching/ece599/papers/rdr_paper34.pdf" rel="nofollow noreferrer">very famous paper</a> (in the networking community), Wang &amp; Crowcroft present some $\mathsf{NP}$-completeness results of path computation under several additive/multiplicative constraints. The first problem is the following :</p>

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

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

<p>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}$.</p>

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

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

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

CC BY-SA 3.0
2016-12-05T13:16:09.673Z
I've checked the paper, this is surely a flaw in their proof.
domotorp
CC BY-SA 3.0
2016-12-05T20:51:50.543Z
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
<np-hardness><reductions>
Validity of exponentiation in a polynomial time reduction
Lamine
# Validity of exponentiation in a polynomial time reduction

(Asked by: username_0 on 2016-12-05)

I asked this question 10 days ago on cs.stackexchange [here](https://cs.stackexchange.com/questions/66367/validity-of-exponentiation-in-a-polynomial-time-reduction) but I didn'y have any answer.

In a [very famous paper](http://eecs.oregonstate.edu/~thinhq/teaching/ece599/papers/rdr_paper34.pdf) (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).

**Tags:** np-hardness, reductions

> **Comments:**
> **username_1**: I've checked the paper, this is surely a flaw in their proof.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2016-12-05. Score: 9 | Accepted answer

The proof as presented in the paper is not conclusive.

However, the stated result itself is correct. It can easily be derived by slightly changing the reduction and by using SUBSET PRODUCT instead of SUBSET SUM.

A useful link for the SUBSET PRODUCT problem:  
<https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete>


---

