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:
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 szer , gdzie W i otrzymują liczby dodatnie (przykład: Ograniczenie opóźnienia i koszt w sieci).
Autorzy dowodzą, że problem ten jest -Complete dostarczając wielomianu redukcji z partycji.
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 .
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.
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).
źródło
Odpowiedzi:
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
źródło