„Trudny” problem może stać się praktyczny, gdy trudność zamkniemy w małym parametrze
Złożoność parametryzowana nie pyta tylko o całkowity rozmiar wejścia n. Wybiera dodatkowy parametr k — na przykład liczbę wyjątków, wielkość szukanego rozwiązania albo szerokość struktury — i próbuje uzyskać czas f(k)·n^c, gdzie wykładnik c nie zależy od k. Takie problemy nazywa się fixed-parameter tractable, FPT. Funkcja f(k) może rosnąć bardzo szybko, nawet wykładniczo, ale jeśli k pozostaje małe, ogromne n nie musi być zabójcze. To inny sposób radzenia sobie z NP-trudnością: zamiast udawać, że całe wejście jest łatwe, izolujemy część odpowiedzialną za eksplozję kombinatoryczną.
Jedna liczba n może ukrywać ważną strukturę
Klasyczna analiza mówi zwykle: wejście ma rozmiar n, jak rośnie czas? Dwa przypadki o takim samym n mogą jednak różnić się cechą, która naprawdę generuje trudność. W harmonogramie może nią być liczba konfliktów, w grafie wielkość szukanego pokrycia, w analizie strukturalnej — szerokość drzewa. Parametryzacja czyni tę cechę drugim wymiarem analizy.
Definicja FPT
Problem parametryzowany należy do FPT, jeżeli można go rozwiązać w czasie f(k)·n^O(1), gdzie f jest dowolną obliczalną funkcją zależną wyłącznie od k. Najważniejsze jest to, że stopień wielomianu w n jest stały i nie rośnie wraz z k. Czas 2^k·n^2 jest FPT; czas n^k nie jest FPT według tej definicji. Jeśli k=10, pierwszy zapis może być rozsądny nawet dla bardzo dużego n, podczas gdy drugi szybko eksploduje.
Przykład: Vertex Cover
Klasyczny Vertex Cover jest NP-zupełny, ale gdy pytamy, czy istnieje pokrycie o rozmiarze najwyżej k, można zbudować prosty algorytm rozgałęziający. Dla dowolnej krawędzi {u,v} przynajmniej jeden z jej końców musi trafić do pokrycia, więc rozważamy dwa przypadki i zmniejszamy k. Powstaje drzewo o rozmiarze rzędu 2^k, a praca poza nim jest wielomianowa. Eksplozja została przeniesiona z całego n do parametru k.
Mały parametr jest warunkiem, nie cudownym rozwiązaniem
Jeżeli k rośnie razem z n, f(k) może znowu stać się niepraktyczne. FPT nie oznacza więc „problem NP-trudny stał się zawsze szybki”. Oznacza precyzyjnie, że trudność można odseparować do jednego parametru. W zastosowaniach wartość takiej analizy zależy od tego, czy parametr rzeczywiście bywa mały w danych, które nas interesują.
Nowe pytanie zamiast szybszego komputera
Gdy problem okazuje się trudny w klasycznym sensie, można zapytać: „co w naszych instancjach jest małe?”. To często prowadzi do algorytmów, kernelizacji i reguł redukcji danych. Zamiast ścigać się ze wzrostem n sprzętem, zmieniamy perspektywę na strukturę wejścia. Granica obliczeń pozostaje, ale może przebiegać w wymiarze, który w praktyce jest kontrolowany.
FPT to coś więcej niż „dobrze działa dla małego k”
W złożoności parametryzowanej kluczowa jest postać czasu f(k)·n^c, gdzie c nie zależy od parametru k. Cała potencjalnie gwałtowna zależność może zostać zamknięta w f(k), natomiast wzrost względem głównego rozmiaru wejścia n pozostaje wielomianowy o stałym wykładniku. To odróżnia FPT od algorytmów typu n^k: one również mogą być praktyczne dla k=2 czy 3, lecz wykładnik rośnie wraz z parametrem i formalnie należą do szerszej klasy XP. Różnica staje się ogromna, gdy n liczy miliony. Parametryzacja pyta więc nie tylko „czy k jest małe?”, ale „czy udało się odseparować k od wykładnika przy n?”.
Dobry parametr powinien odpowiadać rzeczywistej strukturze
Parametr k nie jest magiczną liczbą dopisywaną do problemu. Największą wartość ma wtedy, gdy w realnych danych rzeczywiście pozostaje mały: może oznaczać liczbę wyjątków, szerokość struktury, wielkość poszukiwanego rozwiązania albo liczbę elementów „odpowiedzialnych” za trudność. Jeżeli k rośnie niemal tak samo jak n, nawet formalnie FPT algorytm może nie dawać praktycznej korzyści. Analiza parametryzowana pomaga więc nazwać warunek, pod którym trudny problem staje się osiągalny.