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

może zostać do nich zredukowany w [[złożoność obliczeniowa|czasie wielomianowym]] - rozwiązanie jednego takiego problemu w czasie wielomianowym oznaczałoby, że <math>P=NP\,</math>. Aby udowodnić, że problem A jest NP-zupełny wystarczy wykazać dla dowolnie wybranego problemu NP-zupełnego B, że dla każdego zestawu danych dla problemu B istnieje przekształcenie (wykonywalne w czasie wielomianowym) tych danych do takich danych problemu A, że dla tego problemu dane te dają tę samą odpowiedź. Owe wielomianowe przekształcenie nazywamy transformacją wielomianową (lub alfa-transformacją). Pierwszym problemem dla którego wykazano NP-zupełność był problem sat-3 czyli problem spełnialności wyrażeń w postaci 3CNF (formuły logiczne składające się z iloczynu logicznego 3-elementowych sum logicznych) rzecz jasna przynależności do klasy NPC nie można było dokonać w sposób powyższy. Zamiast tego wykazano możliwość sprowadzenia do niego każdego problemu należącego do klasy NP.

 

 

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 czasie wielomianowym wszystkie problemy NP-zupełne.