Validité de l'exponentiation dans une réduction de temps polynomiale

J'ai posé cette question il y a 10 jours sur cs.stackexchange ici mais je n'ai pas eu de réponse.

Dans un article très célèbre (dans la communauté des réseaux), Wang et Crowcroft présentent des résultats de complétion du calcul de chemin sous plusieurs contraintes additives / multiplicatives. Le premier problème est le suivant: $\mathsf{NP}$

Étant donné un graphique orienté et deux métriques de poids et sur les bords, définissez, pour un chemin , ( ). Étant donné deux nœuds et , le problème est de trouver un chemin de à st , où les reçoivent des nombres positifs (exemple: contrainte de retard et coût dans un réseau). $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$

Les auteurs prouvent que ce problème est -complet en fournissant une réduction polynomiale de PARTITION. $\mathsf{NP}$

Ils posent alors le même problème sauf que les métriques sont multiplicatives, c'est-à-dire . Afin de prouver que la version multiplicative est -complète, ils fournissent une réduction "polynomiale" de la version additive simplement en mettant et . $w'_i(P)=\prod_{a\in P}w'_i(a)$ $\mathsf{NP}$ $w'_i(a)=e^{w_i(a)}$ $W'_i=e^{W_i}$

Je suis très perplexe devant cette réduction. Puisque et font partie de l'entrée (en binaire, je suppose), alors leetne sont pas polynômes danset. La réduction n'est donc pas polynomiale. $W'_i$ $w'_i(a)$ $|w'_i(a)|$ $|W'_i|$ $|w_i(a)|$ $|W_i|$

Suis-je en train de manquer quelque chose de trivial ou y a-t-il une faille dans la preuve? Mon doute porte sur la validité de la preuve, même si le résultat est clairement vrai.

Référence de l'article: Zheng Wang, Jon Crowcroft. Routage de qualité de service pour la prise en charge des applications multimédia . Journal de l'IEEE sur certains domaines des communications 14 (7): 1228-1234 (1996).

np-hardness reductions Lamine
la source

J'ai vérifié le papier, c'est sûrement une faille dans leur épreuve.

domotorp

Le document est cité plus de 2000 fois. C'est effrayant ...

Lamine

Eh bien, la plupart des citations n'utilisent probablement pas ce résultat particulier, et aussi, après tout, c'est toujours vrai. On m'a donné des exemples où ils ont dû retirer plusieurs documents en s'appuyant sur un faux résultat. De plus, cette astuce d'exponentiation est si standard que la plupart des gens n'y réfléchissent même pas et ne réalisent pas ce que vous avez fait, que la longueur de l'entrée change.

domotorp

Validité de l'exponentiation dans une réduction de temps polynomiale

Réponses: