P versus NP to podstawowe pytanie informatyki teoretycznej i matematyki: czy każdy problem, którego rozwiązanie można szybko (efektywnie) sprawdzić przez komputerami, może być też szybko rozwiązany przez komputery? Mówiąc konkretniej, P i NP to dwie klasy problemów decyzyjnych: P to klasa problemów rozwiązywalnych przez deterministyczną maszynę Turinga w czasie wielomianowym (czyli „szybko” w sensie złożoności obliczeniowej), natomiast NP to klasa problemów, dla których prawdziwość odpowiedzi „tak” można zweryfikować w czasie wielomianowym, jeśli zostanie podany odpowiedni certyfikat (również równoważnie: dają się rozwiązać przez niedeterministyczną maszynę Turinga w czasie wielomianowym). W potocznym ujęciu: problemy z P są „łatwe do rozwiązania”, a problemy z NP są „łatwe do sprawdzenia”.

Czym są P i NP — nieco dokładniej

Termin „czas wielomianowy” oznacza, że czas działania algorytmu jest ograniczony wielomianem względem rozmiaru wejścia (np. n, n^2, n^3). Klasa P obejmuje problemy decyzyjne, dla których istnieje algorytm deterministyczny działający w czasie wielomianowym. Klasa NP obejmuje problemy, dla których każda instancja ze słuszną odpowiedzią „tak” posiada krótki dowód (certyfikat), który można sprawdzić deterministycznie w czasie wielomianowym.

NP-zupełność i redukcje

W ramach NP wyróżniono podklasę najtrudniejszych problemów — NP-zupełne (NP-complete). Problem jest NP-zupełny jeśli (1) należy do NP oraz (2) każdy problem z NP można do niego sprowadzić w czasie wielomianowym (tzw. redukcja wielomianowa). Jeśli ktokolwiek znajdzie algorytm wielomianowy dla jednego problemu NP-zupełnego, to automatycznie otrzymamy algorytmy wielomianowe dla wszystkich problemów w NP, czyli P = NP. Najważniejszy wynik w tej dziedzinie to Twierdzenie Cooka–Levina (Cook 1971, niezależnie Levin), które pokazało, że problem SAT (spełnialność formuł logicznych) jest NP-zupełny. Później Richard Karp opisał wiele innych klasycznych problemów NP-zupełnych (m.in. w pracy 1972).

Historia

Już w 1956 roku Kurt Gödel pisał do Johna von Neumanna o zagadnieniach związanych z efektywnością dowodzenia i pytał, czy niektóre problemy bardzo trudne teoretycznie mogą dać się rozwiązać w czasie kwadratowym lub liniowym. Precyzyjne sformułowanie problemu P versus NP przypisuje się Stephenowi Cookowi (1971), który sformalizował pojęcie NP-zupełności w artykule "The complexity of theorem proving procedures".

Dlaczego problem jest ważny?

Rozstrzygnięcie, czy P = NP, miałoby daleko idące konsekwencje praktyczne i teoretyczne:

  • Jeśli P = NP: wiele problemów uważanych dziś za trudne (optymalizacja kombinatoryczna, planowanie, rozkład faktów, wiele problemów logicznych) stałoby się teoretycznie „łatwe” — istniałby algorytm wielomianowy rozwiązujący je wszystkie. To oznaczałoby rewolucję w kryptografii (większość obecnych systemów kryptograficznych opiera się na domniemanej trudności pewnych problemów), w rozwiązywaniu zadań optymalizacyjnych w nauce i przemyśle oraz w automatycznym dowodzeniu twierdzeń.
  • Jeśli P ≠ NP: potwierdziłoby to, że istnieją problemy o fundamentalnie wyższej złożoności obliczeniowej — nie da się ich rozwiązać szybko, choć można szybko sprawdzać poprawność propozycji rozwiązań. To uzasadnia użycie heurystyk, algorytmów przybliżonych, metod numerycznych i podejść typu parametr FPT (fixed-parameter tractable) w praktyce.

Przykłady problemów

Typowe przykłady problemów NP-zupełnych to SAT (spełnialność formuł boolowskich), Problem komiwojażera (decision), Hamiltonian path, Clique, Vertex Cover, Subset Sum i wiele innych. W praktyce dla wielu z tych problemów stosuje się zaawansowane heurystyki, algorytmy approximacyjne, algorytmy dokładne o czasie wykładniczym, a także metody specjalizowane dla konkretnego typu danych.

Stan wiedzy i nagroda milenijna

Do dziś (stan na moment publikacji tego artykułu) nie ma powszechnie zaakceptowanego dowodu ani na P = NP, ani na P ≠ NP — problem pozostaje otwarty i aktywnie badany przez matematyków i informatyków. Z tego powodu jest on uznawany za jedno z najważniejszych pytań w nauce komputerów i matematyce teoretycznej. Jest to także jedno z siedmiu problemów milenijnych wybranych przez Clay Mathematics Institute, w których za znalezienie poprawnego rozwiązania przewidziana jest nagroda w wysokości 1 000 000 USD.

Uwagi praktyczne

Nawet bez formalnego rozstrzygnięcia wiele narzędzi i teorii rozwinięto, aby radzić sobie z problemami NP w praktyce: algorytmy przybliżone (approximation algorithms), metody heurystyczne (np. algorytmy genetyczne, symulowane wyżarzanie), programowanie całkowite z wykorzystaniem silnych relaksacji oraz teoria złożoności parametrów (fixed-parameter tractability). Społeczność naukowa nadal poszukuje głębszego zrozumienia struktury klas złożoności i możliwości nowych technik algorytmicznych.