Validade da exponenciação em uma redução de tempo polinomial

Eu fiz essa pergunta há 10 dias no cs.stackexchange aqui, mas não tive nenhuma resposta.

Em um artigo muito famoso (na comunidade de redes), Wang & Crowcroft apresentam alguns resultados de da computação de caminhos, sob várias restrições aditivas / multiplicativas. O primeiro problema é o seguinte: $\mathsf{NP}$

Dado um gráfico direcionado e duas métricas de peso e sobre as arestas, defina, para um caminho , ( ). Dado dois nós e , o problema é encontrar um caminho de a r , onde o são dados números positivos (exemplo: Atraso de restrição e de custo em uma rede). $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$

Os autores provam que esse problema é completo, fornecendo uma redução polinomial de PARTITION. $\mathsf{NP}$

Então eles apresentam o mesmo problema, exceto que as métricas são multiplicativas, ou seja, . Para provar que a versão multiplicativa é , eles fornecem uma redução "polinomial" da versão aditiva apenas colocando e . $w'_i(P)=\prod_{a\in P}w'_i(a)$ $\mathsf{NP}$ $w'_i(a)=e^{w_i(a)}$ $W'_i=e^{W_i}$

Estou muito intrigado com essa redução. Como e fazem parte da entrada (em binário, eu acho), então o e não são polinomiais em e . Portanto, a redução não é polinomial. $W'_i$ $w'_i(a)$ $|w'_i(a)|$ $|W'_i|$ $|w_i(a)|$ $|W_i|$

Estou perdendo algo trivial ou há uma falha na prova? Minha dúvida é sobre a validade da prova, mesmo que o resultado seja claramente verdadeiro.

Referência do artigo: Zheng Wang, Jon Crowcroft. Roteamento de qualidade de serviço para aplicativos de multimídia de suporte . Revista IEEE sobre Áreas Selecionadas em Comunicações 14 (7): 1228-1234 (1996).

np-hardness reductions Lamine
fonte

Eu verifiquei o jornal, isso certamente é uma falha na prova deles.

Domotorp 5/12

O artigo é citado mais de 2000 vezes. Isso é assustador ...

Lamine

Bem, provavelmente a maioria das citações não usa esse resultado específico e, afinal, ainda é verdade. Disseram-me exemplos quando eles tiveram que retirar vários papéis com base em um resultado falso. Além disso, esse truque de exponenciação é tão padrão que provavelmente a maioria das pessoas nem pensa nisso e percebe o que você fez, que a duração da entrada muda.

Domotorp 5/12

Validade da exponenciação em uma redução de tempo polinomial

Respostas: