Algorytm może wyglądać wielomianowo, dopóki nie policzymy bitów
Klasyczny problem plecakowy ma programowanie dynamiczne działające w czasie O(n·C), gdzie n to liczba przedmiotów, a C — pojemność plecaka wyrażona jako liczba całkowita. Na pierwszy rzut oka to wielomian. Problem w tym, że wielkością wejścia jest liczba bitów potrzebnych do zapisania C, czyli około log2 C. Jeżeli C jest ogromne, algorytm zależny od samej wartości C może być wykładniczy względem długości jej zapisu. Taki czas nazywa się pseudowielomianowym. Plecak jest słabo NP-trudny właśnie w sposób zgodny z istnieniem takich algorytmów. To lekcja, że w analizie złożoności nie pytamy tylko „jak duża jest liczba?”, lecz „ile informacji trzeba było dostarczyć, aby ją zapisać?”.
Plecak i tablica dynamiczna
W podstawowej wersji mamy n przedmiotów o całkowitych wagach i wartościach oraz pojemność C. Dynamic programming może budować tabelę odpowiadającą możliwym pojemnościom od 0 do C. Daje to klasyczny czas rzędu O(nC). Dla C=10 000 taka metoda może być bardzo praktyczna. Jeśli jednak C ma wartość około 2^100, nikt nie wpisuje do pliku 2^100 znaków — sama liczba ma jedynie około 101 bitów zapisu binarnego.
Wartość liczby to nie długość wejścia
Złożoność wielomianową mierzy się względem długości zakodowanego wejścia. Liczba C potrzebuje Θ(log C) bitów. Funkcja C jest więc wykładnicza względem log C. Algorytm O(nC) nie jest ogólnie wielomianowy względem długości binarnego wejścia, choć jest wielomianowy względem numerycznej wartości C. Stąd termin „pseudowielomianowy”. To subtelność, która potrafi zmienić klasyfikację algorytmu bez zmiany ani jednej instrukcji jego kodu.
Słaba NP-trudność
Klasyczny problem plecakowy jest NP-trudny w słabym sensie i ma algorytmy pseudowielomianowe. W literaturze dokładnie ta cecha odróżnia go od problemów silnie NP-trudnych, dla których nie oczekujemy algorytmu pseudowielomianowego, chyba że P=NP. Plecak jest dlatego bardzo dobrym laboratorium do obserwowania, jak ogromne wartości liczbowe mogą być źródłem teoretycznej trudności.
Ten sam input, dwie skale
Jeśli pojemność C rośnie z miliona do miliarda, zapis binarny wydłuża się tylko o około dziesięć bitów, natomiast tablica O(C) rośnie tysiąckrotnie. W praktyce pokazuje to, dlaczego analiza „liczba operacji jako funkcja największej wartości parametru” może być zwodnicza. Komputer dostał niewiele więcej danych, ale algorytm generuje ogromnie więcej pracy.
Dlaczego to ważne poza plecakiem
Ta zasada dotyczy wszystkich problemów z dużymi liczbami: kosztami, czasami, wagami, pojemnościami i współczynnikami. Kodowanie unarne i binarne może prowadzić do zupełnie innej oceny złożoności. Teoria obliczeń patrzy na długość reprezentacji, ponieważ to ona mierzy ilość informacji przekazanej algorytmowi. Dzięki temu „wielomianowy” ma znaczenie niezależne od przypadkowej skali liczb w danych.
„Słabo NP-trudny” to ważne zastrzeżenie
Klasyczny problem plecakowy jest przykładem problemu słabo NP-trudnego. Oznacza to między innymi, że jego trudność jest silnie związana z dużymi wartościami liczbowymi zapisanymi zwięźle w systemie binarnym. Algorytm dynamiczny zależny od pojemności C może być bardzo dobry, gdy C jest małe lub umiarkowane, choć formalnie nie jest wielomianowy względem liczby bitów potrzebnych do zapisania C. To odróżnia plecak od problemów silnie NP-trudnych, gdzie podobny ratunek przez małe wartości liczb nie wystarcza. Pseudowielomianowość nie jest więc tylko terminologiczną ciekawostką: mówi, kiedy „trudny problem” może stać się łatwy po ograniczeniu wielkości parametrów liczbowych.
Jednostka miary czasu potrafi ukryć problem
Mówienie, że algorytm działa w O(nC), brzmi niewinnie, dopóki C nie jest liczbą zapisaną w zaledwie kilkudziesięciu bitach, ale mającą ogromną wartość. Wtedy liczba operacji może być wykładnicza względem długości wejścia. To dlatego złożoność liczy rozmiar reprezentacji, a nie wartość symbolizowaną przez zapis. Ten sam szczegół pojawia się w wielu problemach numerycznych i jest kluczowy dla poprawnego rozumienia słowa „wielomianowy”.