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

Usunięte 9 bajtów ,  14 lat temu
Mocniejszy wniosek.
(linki)
(Mocniejszy wniosek.)
'''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.
2677

edycji