Tysiące różnych trudnych zadań łączy sieć redukcji
NP-zupełność ujawniła zaskakującą jedność między problemami wyglądającymi na niepowiązane. Redukcja wielomianowa jest algorytmicznym „tłumaczeniem”: przekształca przypadek jednego problemu w przypadek drugiego tak, aby odpowiedź została zachowana. Twierdzenie Cooka z 1971 r. pokazało fundamentalną kompletność problemu logicznego związanego z SAT, a Richard Karp w 1972 r. wykazał podobne relacje dla szerokiej grupy problemów kombinatorycznych. Efekt jest niezwykły: szybki algorytm dla jednego problemu NP-zupełnego dałby szybkie algorytmy dla wszystkich problemów w NP. Trudność może więc być przenoszona między logiką, grafami, harmonogramami i innymi dziedzinami.
Redukcja to kontrolowane tłumaczenie
Załóżmy, że chcemy rozwiązać problem A, ale mamy świetny program do problemu B. Jeżeli potrafimy w czasie wielomianowym przekształcić dowolne wejście A w wejście B tak, aby „tak” dla A zachodziło dokładnie wtedy, gdy „tak” zachodzi dla B, możemy użyć rozwiązującego B programu jako podprocedury dla A. Taka redukcja mówi coś więcej niż „problemy są podobne”: formalnie pokazuje, że B jest co najmniej tak trudny jak A względem rozważanego modelu obliczeń.
Cook i początek kompletności
W 1971 roku Stephen Cook pokazał, że problemy obliczane przez niedeterministyczne maszyny w czasie wielomianowym można kodować jako odpowiedni problem logiki zdań. Współczesne ujęcie tego wyniku prowadzi do twierdzenia Cooka–Levina o NP-zupełności SAT. To był przełom koncepcyjny: zamiast badać każdy trudny problem w izolacji, można było udowadniać jego trudność przez redukcję z problemu już znanego jako kompletny.
Karp zbudował mosty do kombinatoryki
Rok później Richard Karp opublikował klasyczną pracę „Reducibility Among Combinatorial Problems”. Pokazał, jak poprzez redukcje wiązać ze sobą wiele problemów dotyczących grafów, pokryć, wyboru podzbiorów i innych struktur kombinatorycznych. Powstała metoda, która do dziś jest standardowym sposobem klasyfikowania problemów: zamiast próbować dowodzić trudności od zera, redukuje się znany problem NP-zupełny do nowego.
Efekt domina
Jeżeli problem B jest NP-zupełny i ktoś znajduje dla niego algorytm wielomianowy, to każdą instancję dowolnego problemu A z NP można najpierw wielomianowo przetłumaczyć na B, a następnie szybko rozwiązać. Całość pozostaje wielomianowa. Właśnie stąd bierze się ogromne znaczenie pojedynczego przełomu: nie byłby to tylko lepszy algorytm dla jednej zagadki, lecz wynik dotyczący całej klasy problemów.
Te same granice nie znaczą tej samej praktyki
Redukcje są narzędziem teorii najgorszego przypadku. Dwa problemy NP-zupełne mogą bardzo różnić się praktyczną trudnością, strukturą danych i skutecznością solverów. Jeden może mieć świetne heurystyki dla typowych instancji, drugi znacznie gorsze. NP-zupełność nie mówi więc, że wszystkie problemy zachowują się identycznie na rzeczywistych danych; mówi, że pod względem wielomianowych redukcji należą do wspólnego rdzenia trudności.
Kierunek redukcji ma znaczenie
W dowodach NP-trudności bardzo łatwo odwrócić logikę. Aby pokazać, że nowy problem B jest co najmniej tak trudny jak znany problem A, trzeba umieć przekształcać instancje A w instancje B, czyli pokazać A ≤p B. Wtedy szybki solver B rozwiązywałby także A. Redukcja w przeciwną stronę mówi coś innego: że A potrafi przejąć pracę problemu B, więc nie dowodzi trudności B. Ta asymetria jest jednym z powodów, dla których redukcje są czymś więcej niż luźną analogią między zadaniami. Tworzą precyzyjną relację „gdybym umiał szybko rozwiązać to, potrafiłbym szybko rozwiązać również tamto”, a cała sieć NP-zupełności opiera się właśnie na pilnowaniu tego kierunku.
Redukcja nie musi zachowywać wyglądu problemu
Przekształcenie może całkowicie zmienić język zadania: zmienne logiczne mogą stać się wierzchołkami grafu, a warunki logiczne — specjalnymi konstrukcjami krawędzi. Liczy się nie podobieństwo powierzchowne, lecz zachowanie odpowiedzi i wielomianowy koszt transformacji. Dzięki temu redukcje odkrywają wspólną strukturę trudności w problemach, które na pierwszy rzut oka nie mają ze sobą nic wspólnego.