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^[1]. 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ż ${\displaystyle P\neq NP}$ (nie udowodniono także przeciwnie, że ${\displaystyle 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.

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

Przykłady

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

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

Zobacz też

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

Przypisy

1. Christos H Papadimitriou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 182, 192. ISBN 83-204-2659-6.