Przegląd

Problem NP-trudny (NP-hard) to pojęcie z teorii złożoności obliczeniowej opisujące problemy przynajmniej tak trudne jak najtrudniejsze problemy ze zbioru NP. W praktyce oznacza to, że każdy problem należący do NP można sprowadzić (zwykle w sensie redukcji wielomianowej) do problemu NP-trudnego. Termin dotyczy głównie zagadnień decyzyjnych i formalizuje intuicję o "trudności" rozwiązywania komputerowo pewnych zadań.

Definicje i relacje

W skrócie: NP to klasa problemów decyzyjnych, których poprawność rozwiązania można sprawdzić w czasie wielomianowym. Problem jest NP-trudny, jeśli każdy problem z NP można do niego sprowadzić. Jeśli dodatkowo sam jest w NP, to nazywa się NP-zupełnym (NP-complete). Zatem: NP-zupełne = NP ∩ NP-trudne. Rozważania te zależą od rodzaju redukcji; najczęściej używana jest redukcja wielomianowa (polynomial-time many-one reduction).

Przykłady

W praktyce wiele znanych zadań optymalizacyjnych ma wersję decyzyjną, która jest NP-zupełna, a wersja optymalizacyjna bywa NP-trudna. Typowe przykłady to:

  • Problem spełnialności formuł boolowskich (SAT, 3‑SAT) — pierwszy udowodniony NP-zupełny przez twierdzenie Cooka-Levina.
  • Decyzyjna wersja problemu komiwojażera (TSP): "czy istnieje cykl odwiedzający wszystkie miasta o długości nie większej niż K?" — wersja ta jest NP-zupełna dla ogólnych kosztów.
  • Wiele problemów kombinatorycznych i grafowych (kolorowanie grafu, plecak w wersji decyzyjnej, problem klik) również należy do tej klasy.

Przykład ilustrujący naturę NP-zupełności: komiwojażer, który chce odwiedzić 100 miast w limicie odległości 10 000 km — jeśli wystarczy sprawdzić pojedynczą trasę w czasie wielomianowym, to znalezienie takiej trasy jest trudniejsze i sprowadza się do ogólnego problemu TSP. Zobacz też więcej o TSP.

Problemy poza NP

Niektóre problemy NP-trudne nie należą do NP — mogą być trudniejsze w sensie teoretycznym lub nawet nierozstrzygalne. Przykładem rodzaju trudnych problemów spoza NP jest problem stopu (czy program zatrzyma się dla danego wejścia), który jest nierozstrzygalny. W literaturze często rozróżnia się klasy obliczalności i stosuje różne rodzaje redukcji, dlatego warto zachować ostrożność przy przenoszeniu wniosków między nimi.

Znaczenie praktyczne i strategie

Problemy NP-trudne mają fundamentalne znaczenie w informatyce teoretycznej i praktyce algorytmicznej. Brak znanych algorytmów wielomianowych dla NP-zupełnych problemów (a otwarte pytanie P vs NP) powoduje, że w zastosowaniach stosuje się różne podejścia: heurystyki, algorytmy przybliżone, metody probabilistyczne, programowanie całkowitoliczbowe, algorytmy eksponencjalne zoptymalizowane praktycznie lub algorytmy parametryzowane. Wiele systemów inżynierskich i optymalizacyjnych opiera się na takich narzędziach.

Historia i konsekwencje teoretyczne

Klasy NP, NP-trudne i NP-zupełne ukształtowały się w połowie XX wieku; kluczowe wyniki to twierdzenie Cooka-Levina oraz praca Richarda Karpa, który pokazał redukcje pomiędzy szeregiem praktycznych problemów. Od tamtej pory identyfikowanie NP-zupełności pomaga zrozumieć, które zadania prawdopodobnie nie mają szybkich algorytmów dokładnych i kieruje badania ku alternatywnym metodom rozwiązywania.

Gdzie szukać dalej

Dalszą lekturę i formalne dowody znajdziesz w literaturze dotyczącej złożoności obliczeniowej oraz w artykułach poświęconych SAT, TSP i twierdzeniom o redukcjach. Przydatne zasoby i kompilacje problemów znajdują się pod odnośnikami: lista problemów NP-zupełnych i przegląd metod sprawdzania rozwiązań.