Problem z plecakiem - NP-kompletny pomimo dynamicznego rozwiązania programistycznego?

Problemy z plecakiem można łatwo rozwiązać za pomocą programowania dynamicznego. Programowanie dynamiczne przebiega w czasie wielomianowym; dlatego to robimy, prawda?

Przeczytałem, że jest to w rzeczywistości problem NP-zupełny, co oznaczałoby, że rozwiązanie problemu wielomianowego jest prawdopodobnie niemożliwe.

Gdzie jest mój błąd?

complexity-theory np-complete dynamic-programming Strin
źródło

Należy pamiętać, że DP jest wielomianem w „rozmiarze tabeli”. Stół jest wykładniczo duży dla Plecaka (patrz odpowiedź Kaveha).

Raphael

Odpowiedzi:

Problem z plecakiem jest gdy liczby są podawane jako liczby binarne . W takim przypadku programowanie dynamiczne zajmie wykładniczo wiele kroków (w wielkości wejścia, tj. Liczby bitów na wejściu), aby zakończyć . $\sf{NP\text{-}complete}$ $\dagger$

Z drugiej strony, jeśli liczby na wejściu zostaną podane pojedynczo, programowanie dynamiczne będzie działać w czasie wielomianowym (w wielkości wejścia).

Tego rodzaju problemy nazywane są słabo $\sf{NP\text{-}complete}$ .

$\dagger$ : Innym dobrym przykładem na zrozumienie znaczenia kodowania używanego do wprowadzania danych jest rozważenie zwykłych algorytmów, aby sprawdzić, czy liczba pierwsza jest liczbą od do i sprawdzić, czy którykolwiek z nich dzieli . Jest to wielomian w ale niekoniecznie w rozmiarze wejściowym. Jeśli podano w formacie binarnym, rozmiar danych wejściowych wynosi a algorytm działa w czasie który jest wykładniczy w wielkości wejściowej. A typową złożonością obliczeniową problemu jest rozmiar danych wejściowych. $2$ $\sqrt{n}$ $n$ $n$ $n$ $\lg n$ $O(\sqrt{n}) = O(2^{\lg n/2})$

Ten rodzaj algorytmu, tj. Wielomian w największej liczbie, która jest częścią danych wejściowych, ale wykładniczo w długości danych wejściowych, nazywa się pseudo-wielomianem .

Kaveh
źródło

Ale pomyśl o przedmiotach, które mają być umieszczone w plecaku. Obiekty muszą być wprowadzone i takie wejście musi być wielomianowe z liczbą obiektów. Jeśli obiektów jest wystarczająco dużo, dane wejściowe są wielomianowe z rozmiarem problemu. Dlaczego więc nie mogę powiedzieć, że problem plecaka jest problemem P pod względem wielkości stołu? Czy się mylę?

Strin,

@Strin, nie, niewielka liczba przedmiotów może wystarczyć, aby poczuć duży plecak, np. Jeśli rozmiar plecaka wynosi , wystarczy jeden przedmiot wielkości . Rozmiar wejścia wynosi około , znacznie mniej niż . (Zakładam, że mówimy o plecaku 0-1.)

m

$m$

m

$m$

2 \lg m

$2\lg m$

m

$m$

Kaveh

Czy można podzielić dane wejściowe na mniejsze, których kodowanie binarne ma rozmiar kończący algorytm w czasie wielomianowym, a następnie połączyć rozwiązania?

Char

@Kaveh „Rozmiar danych wejściowych wynosi około 2 lg m” Nie rozumiem, skąd bierzesz tę część. Związek między m(wielkością opakowania) a n(liczbą przedmiotów) jest całkowicie nieznany, prawda? I ponownie „kiedy liczby są podawane jako liczby binarne” ... ale czy nie możesz tego powiedzieć na nic? W przypadku większości algorytmów mówimy o wielkości wejściowej w bazie 10. Po co tutaj mówić o pliku binarnym? I to, czy kodujesz w formacie binarnym, ósemkowym, dziesiętnym itp. ... actualliczba iteracji w głównej pętli algorytmu zależy bezpośrednio od obu ni W.

The111

@ The111, myślę, że lepiej będzie, jeśli opublikujesz to jako nowe pytanie, a ja odpowiem. Myślę, że twoje pytanie jest bardziej fundamentalne i komentarze nie są zbytnio związane z tym pytaniem.

Kaveh

Główne zamieszanie polega na różnicy między „ rozmiarem ” a „ wartością ”.

„ Czas wielomianowy ” oznacza wielomian wrt wielkości wejściowej.

„ Czas pseudopolinomalny ” oznacza, że wielomian wrt wartości wejściowej. Można pokazać (poniżej), że jest to równoważne z wykładniczym względem wielkości danych wejściowych.

Innymi słowy: Niech reprezentuje rozmiar danych wejściowych, a reprezentuje wartość danych wejściowych. $N_{size}$ $N_{val}$

Czas wielomianu: dla $O(N_{size}^x)$ $x\in\mathbb{N}$

Pseudopol. Czas: dla $O(N_{val}^x)$ $x\in\mathbb{N}$

Teraz problem plecakowy ma rozwiązanie pseudopolomiczne, a nie wielomianowe , ponieważ rozwiązanie programowania dynamicznego daje czas działania zależny od wartości - tj. , gdzie jest wartością reprezentującą maksymalną pojemność. $O(nW)$ $W$

Teraz wartość można przekonwertować na rozmiar , reprezentując ją w liczbie cyfr potrzebnych do jej przedstawienia. mówi, ile cyfr potrzeba do reprezentowania przy użyciu podstawy . Można to rozwiązać, aby dał: $N_{size}=Log_b(N_{val})$ $N_{val}$ $b$ $N_{val}$

N_{v a l} = b^{N_{s i z e}}

$N_{val}=b^{N_{size}}$

Podłączenie tego do definicji czasu pseudopolomicznego pokazuje, że jest to wykładniczy wr_ : $N_{size}$

Pseudopol. Czas: dla $O(b^{xN_{size}})$ $b, x\in\mathbb{N}$

bcorso
źródło

Utworzono tutaj konto tylko po to, by podziękować! Dopiero po twoim przykładzie w końcu to zrozumiałem.

Inoryy

Twoja odpowiedź bije wszystkich, brawo!

Muhammad Razib,

Aby dodać do tej wspaniałej odpowiedzi, możemy powiedzieć, że jeśli zmienimy W ze 100 na 101, rozmiar problemu nie zostanie zwiększony, rozmiar zostanie zwiększony, jeśli dodamy kolejny bit do W, co czyni go dwa razy większym, więc tabela mają dwa razy więcej wierszy, a zatem wraz ze zwiększeniem rozmiaru o jeden czas problemu jest podwojony, dlatego jest wykładniczy.

Amen,

@bcorso Załóżmy, że otrzymujesz wartość N. I musiałeś znaleźć sumę liczb od 1 do N i użyłeś metody pętli for, która byłaby algorytmem pseudopolinomialnym?

DollarAkshay

Problem plecakowy , jak określono w artykule Karp jest jest NP-zupełny, ponieważ nie jest redukcja od innych problemów NPC (dokładna obejmuje w tym przypadku) do plecaka. Oznacza to, że nie ma algorytmu wielomianowego, który rozwiązałby wszystkie przypadki problemu z plecakiem, chyba że . $\text{P}=\text{NP}$

Istnieją jednak różne warianty (np. 0-1 Knapsack i inne ), które mogą, ale nie muszą mieć rozwiązania wielomianowe lub dobre przybliżenia. Ale to nie to samo, co ogólny problem z plecakiem. Ponadto mogą istnieć wydajne algorytmy, które działają dla określonych (rodzin) instancji , ale algorytmy te będą działać dłużej w innych instancjach.

Ran G.
źródło