Validitas eksponensial dalam pengurangan waktu polinomial

Saya menanyakan pertanyaan ini 10 hari yang lalu di cs.stackexchange di sini tapi saya tidak punya jawaban.

Dalam makalah yang sangat terkenal (di komunitas jaringan), Wang & Crowcroft menyajikan beberapa hasil perhitungan jalur di bawah beberapa kendala aditif / multiplikasi. Masalah pertama adalah sebagai berikut: $\mathsf{NP}$

Diberikan grafik terarah dan dua metrik bobot dan di tepinya, menentukan, untuk jalur , ( ). Diberikan dua node dan , masalahnya adalah menemukan jalur dari ke st , di mana diberi angka positif (contoh: Delay constraint dan biaya dalam jaringan). $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$

Para penulis membuktikan bahwa masalah ini adalah -complete dengan memberikan pengurangan polinomial dari PARTITION. $\mathsf{NP}$

Kemudian mereka menyajikan masalah yang sama kecuali bahwa metrik adalah multiplikatif, yaitu, . Untuk membuktikan versi multiplikatif adalah -complete, mereka memberikan pengurangan "polinomial" dari versi aditif hanya dengan menempatkan dan . $w'_i(P)=\prod_{a\in P}w'_i(a)$ $\mathsf{NP}$ $w'_i(a)=e^{w_i(a)}$ $W'_i=e^{W_i}$

Saya sangat bingung dengan pengurangan ini. Karena dan adalah bagian dari input (dalam biner, saya kira), makadan bukan polinomial dalam dan . Dengan demikian reduksi tidak polinomial. $W'_i$ $w'_i(a)$ $|w'_i(a)|$ $|W'_i|$ $|w_i(a)|$ $|W_i|$

Apakah saya melewatkan sesuatu yang sepele atau ada kekurangan dalam buktinya? Keraguan saya adalah tentang validitas buktinya, meskipun hasilnya jelas benar.

Referensi kertas: Zheng Wang, Jon Crowcroft. Routing Kualitas Layanan untuk Mendukung Aplikasi Multimedia . Jurnal IEEE pada Area yang Dipilih dalam Komunikasi 14 (7): 1228-1234 (1996).

np-hardness reductions Lamin
sumber

Saya sudah memeriksa kertasnya, ini pasti cacat dalam bukti mereka.

domotorp

Makalah ini dikutip lebih dari 2000 kali. Ini menakutkan ...

Lamine

Yah, mungkin sebagian besar kutipan tidak menggunakan hasil khusus ini, dan juga, bagaimanapun juga, itu masih benar. Saya diberi tahu contoh ketika mereka harus menarik beberapa kertas berdasarkan hasil yang salah. Juga, trik eksponensial ini sangat standar sehingga mungkin kebanyakan orang bahkan tidak memikirkannya dan menyadari apa yang Anda lakukan, sehingga panjang inputnya berubah.

domotorp

Validitas eksponensial dalam pengurangan waktu polinomial

Jawaban: