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

15

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:NP

Biorąc pod uwagę ukierunkowany wykres i dwie miary wagi w 1 i w 2 ponad krawędziami, zdefiniuj dla ścieżki P , w i ( P ) = a P w i ( a ) ( i = 1 , 2 ). Biorąc pod uwagę dwa węzły s i t , problemem jest znalezienie ścieżki P od S do pozycji t st szerG=(V,A)w1w2Pwi(P)=aPwi(a)i=1,2stPst , gdzie W i otrzymują liczby dodatnie (przykład: Ograniczenie opóźnienia i koszt w sieci).wi(P)WiWi

Autorzy dowodzą, że problem ten jest -Complete dostarczając wielomianu redukcji z partycji.NP

Następnie przedstawiają ten sam problem, z tym wyjątkiem, że metryki są multiplikatywne, tj. . W celu udowodnienia, wersję zwielokrotniony jest N P -Complete zapewniają one „wielomianu” redukcja do wersji dodatku tylko poprzez umieszczenie w ' I ( ) = e W I ( ) i W " I = e W I .wi(P)=aPwi(a)NPwi(a)=ewi(a)Wi=eWi

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

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

Lamine
źródło
1
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

Odpowiedzi:

9

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