Czym jest NP-trudność (NP-hardness)?
NP-trudność opisuje klasę problemów obliczeniowych, których rozwiązanie jest co najmniej tak wymagające jak najtrudniejsze zadania należące do klasy NP. Oznacza to, że każdy problem z NP można w skończonym, wielomianowym czasie sprowadzić do problemu NP-trudnego. Jeśli więc w praktyce udałoby się znaleźć szybki algorytm dla jednego problemu NP-trudnego, w tym samym momencie poznalibyśmy szybkie metody dla całej klasy NP. Definicję formalną wprowadził w 1971 r. Stephen Cook z Uniwersytetu Toronto oraz, niezależnie, Leonid Levin z Moskiewskiego Uniwersytetu Państwowego, a terminologia utrwaliła się dzięki publikacjom Gareya i Johnsona z Bell Labs w końcu lat 70.
Jak dokładnie działa NP-trudność
Sedno leży w redukcjach: jeśli potrafimy przekształcić dowolny problem z NP na inny problem w czasie wielomianowym, a sam problem docelowy można uznać za NP-trudny, wówczas jego efektywne rozwiązanie pociągnęłoby za sobą efektywne rozwiązania wszystkich problemów z NP. Klasyczne przykłady obejmują problem max-clique, problem pokrycia zbioru oraz komiwojażera w wersji decyzyjnej. Algorytmika AI często spotyka się z NP-trudnością podczas budowy planistów, heurystyk wyszukiwawczych czy systemów wnioskowania o ograniczeniach, gdzie dokładne wyznaczenie optymalnego wyniku wymaga rozważenia wykładniczej liczby konfiguracji.
Zastosowania w praktyce
W uczeniu maszynowym klasyfikacja struktur białka, doboru cech czy optymalnej architektury sieci neuronowych bywa sprowadzana do problemów NP-trudnych. Planowanie ruchu wieloagentowego, kompresja danych z gwarancją błędu czy kalibracja dużych modeli językowych również przywołują zadania tej klasy. Przykładowo, wyszukiwanie optymalnego rozkładu uwagi w transformatorach można sprowadzić do wariantu problemu podzbioru, a to oznacza konieczność stosowania aproksymacji lub heurystyk. W systemach rekomendacyjnych NP-trudność pojawia się przy budowie maksymalnie zróżnicowanej listy propozycji, co pokazuje, że nawet pozornie proste funkcje interfejsu użytkownika kryją trudne zagadnienia obliczeniowe.
Zalety i ograniczenia
Zaletą analizy NP-trudności jest jasne określenie granic efektywnego liczenia, co pomaga inżynierom unikać bezowocnych prób tworzenia zbyt ambitnych algorytmów. Dzięki temu łatwiej zaprojektować metaheurystyki, algorytmy przybliżone lub procedury opierające się na losowaniu. Ograniczeniem pozostaje jednak fakt, że etykieta NP-trudny nie daje informacji o praktycznej złożoności wejść występujących w realnych projektach. Wiele zadań oznaczonych jako NP-trudne rozwiązuje się szybko dla konkretnych danych, co otwiera pole do dalszych badań empirycznych.
Na co uważać?
Projektując systemy AI, warto sprawdzić, czy pojawiający się problem jest jedynie wariantem klasycznego zadania NP-trudnego. Jeżeli tak, należy zawczasu przygotować strategię obejmującą heurystyki, relaksacje liniowe lub uczenie maszynowe wspomagające wyszukiwanie. Należy również pamiętać, że dowód NP-trudności oparty o redukcję wymaga starannego skonstruowania operatorów przekształcenia, a niepoprawna redukcja może prowadzić do błędnych wniosków o wydajności systemu.
Dodatkowe źródła
Szczegółową analizę formalną prezentuje hasło NP-trudność na Wikipedii. Historyczny artykuł Stephena Cooka dostępny jest na witrynie ACM. Z kolei praktyczne aspekty omawia przegląd arXiv:1907.12424 dotyczący heurystyk w optymalizacji kombinatorycznej. Wprowadzenie do metod aproksymacyjnych można znaleźć w książce „Approximation Algorithms” autorstwa Vaziraniego, a obszerne zbiory redukcji publikuje MIT OpenCourseWare w materiałach z kursu 6.046J.
