Ważność potęgowania w wielomianowym skrócie czasu

Zadałem to pytanie 10 dni temu na cs.stackexchange tutaj, ale nie miałem żadnej odpowiedzi.

W bardzo słynnego papieru (w środowisku sieciowym), Wang i Crowcroft przedstawić kilka -completeness wyniki obliczeń ścieżki pod kilkoma dodatkami / multyplikatywnych ograniczeń. Pierwszy problem jest następujący: $\mathsf{NP}$

Biorąc pod uwagę ukierunkowany wykres i dwie miary wagi i ponad krawędziami, zdefiniuj dla ścieżki , ( ). Biorąc pod uwagę dwa węzły i , problemem jest znalezienie ścieżki od do st $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$ , gdzie otrzymują liczby dodatnie (przykład: Ograniczenie opóźnienia i koszt w sieci). $w_i(P)\leq W_i$ $W_i$

Autorzy dowodzą, że problem ten jest -Complete dostarczając wielomianu redukcji z partycji. $\mathsf{NP}$

Następnie przedstawiają ten sam problem, z tym wyjątkiem, że metryki są multiplikatywne, tj. . W celu udowodnienia, wersję zwielokrotniony jest -Complete zapewniają one „wielomianu” redukcja do wersji dodatku tylko poprzez umieszczenie i . $w'_i(P)=\prod_{a\in P}w'_i(a)$ $\mathsf{NP}$ $w'_i(a)=e^{w_i(a)}$ $W'_i=e^{W_i}$

Jestem bardzo zaskoczony tą redukcją. Ponieważ i są częścią wejścia (w formacie binarnym, jak sądzę), a następnie i nie są wielomianami w i . Zatem redukcja nie jest wielomianowa. $W'_i$ $w'_i(a)$ $|w'_i(a)|$ $|W'_i|$ $|w_i(a)|$ $|W_i|$

Czy brakuje mi czegoś trywialnego, czy jest wada w dowodzie? Mam wątpliwości co do ważności dowodu, nawet jeśli wynik jest wyraźnie prawdziwy.

Odniesienie do papieru: Zheng Wang, Jon Crowcroft. Jakość routingu usług do obsługi aplikacji multimedialnych . IEEE Journal on Selected Areas in Communications 14 (7): 1228-1234 (1996).

np-hardness reductions

— Lamine
źródło

Sprawdziłem gazetę, to z pewnością wada w ich dowodzie.

— domotorp

Artykuł jest cytowany ponad 2000 razy. To przerażające ...

— Lamine,

Cóż, prawdopodobnie większość cytowań nie korzysta z tego konkretnego wyniku, a przecież nadal jest to prawdą. Powiedziano mi przykłady, kiedy musieli wycofać kilka dokumentów opartych na fałszywym wyniku. Również ta sztuczka potęgowania jest tak standardowa, że prawdopodobnie większość ludzi nawet nie przemyśla i nie zdaje sobie sprawy z tego, co zrobiłeś, że zmienia się długość danych wejściowych.

— domotorp

Dowód przedstawiony w artykule nie jest rozstrzygający.

Jednak sam wynik jest prawidłowy. Można to łatwo uzyskać poprzez nieznaczną zmianę redukcji i użycie SUBSET PRODUCT zamiast SUBSET SUM.

Przydatny link do problemu SUBSET PRODUCT:
/cs/7907/is-the-subset-product-problem-np-complete

— Gamow
źródło