Problem NP-zupełny

Problem NP-zupełny (NPC, ang. NP-Complete) – problem zupełny w klasie NP, ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w takim czasie wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).

Pierwszym problemem, którego NP-zupełność wykazano, był problem SAT, czyli problem spełnialności formuł zdaniowych. Udowodnił to w 1971 roku Stephen Cook.

Pytanie, czy problemy NP-zupełne można rozwiązywać w czasie wielomianowym, jest największą zagadką informatyki teoretycznej. Ciągle nie udowodniono tego, iż $P\not =NP$ (nie udowodniono także przeciwnie, że $P=NP$), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście problemów milenijnych. Mimo ufundowania miliona dolarów za rozwiązanie tak postawionego problemu, nikomu się to nie udało.

Pytanie związane z problemami NP-zupełnymi ma szczególne znaczenie w kryptografii – rozwiązanie któregokolwiek problemu NP-zupełnego w czasie wielomianowym (a zatem rozwiązanie ich wszystkich) umożliwiłoby między innymi szybkie łamanie kryptosystemu RSA (jednego z najbardziej popularnych szyfrów aktualnie stosowanych), gdyż opiera się on na założeniu, że problem podziału dowolnej liczby na czynniki pierwsze nie jest problemem wielomianowym. Problem ten jest w NP, ale nie udowodniono jego NP-trudności.

Problem nie może być jednocześnie NP-zupełny i CoNP-zupełny, chyba że $NP=CoNP$.

Przykłady

Przykłady problemów NP-zupełnych:

• problem cyklu Hamiltona
• problem kliki
• decyzyjna wersja problemu komiwojażera (COMI)
• pokrycie wierzchołkowe
• problem spełnialności (SAT)
• problem trójkolorowalności (3COL)
• kolorowanie grafu
• cykliczne pokrycie krawędziowe
• decyzyjna wersja problemu plecakowego

Zobacz też

• problem NP-trudny
• problem silnie NP-zupełny
• lista problemów NP-zupełnych
• problem NP-pośredni
• problem obliczeniowy