Problem NP-zupełny: Różnice pomiędzy wersjami

m
int.
m (drobne redakcyjne)
m (int.)
'''Problem NP-zupełny''' ('''NPC''', {{Ang.|NP-Complete}}) – [[problem zupełny]] w klasie [[Problem NP|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<ref>{{cytuj książkę |nazwisko=Papadimitriou |imię=Christos H |tytuł=Złożoność obliczeniowa | data=2002 |wydawca=Wydawnictwa Naukowo-Techniczne |miejsce=Warszawa |isbn = 83-204-2659-6 |strony = 182,192}}</ref>. 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 [[Problem spełnialności|SAT]], czyli problem spełnialności formuł zdaniowych. Udowodnił to w 1971 roku [[Stephen Cook]].