Wersja z 21:00, 27 kwi 2007 edytuj Ksoltys (dyskusja \| edycje) 56 edycji linki ← poprzednia edycja		Wersja z 00:44, 13 maj 2007 edytuj anuluj edycję Royas (dyskusja \| edycje) Redaktorzy 2679 edycji Mocniejszy wniosek. następna edycja →
Linia 1: '''Problem NP-zupełny''' (NPC) to problem, który należy do klasy [[Problem NP\|NP]] oraz jest [[Problem NP-trudny\|NP-trudny]]. Innymi słowy, każdy problem należący do NP można zredukować w czasie wielomianowym do problemu NP-zupełnego. 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~~. 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 wykazano NP-zupełność wykazano, był problem 3-[[Problem spełnialności\|SAT]], 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.

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