Problem NP-zupełny: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Mocniejszy wniosek. |
wykazano wykazano |
||
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. 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
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ż <math>P\not=NP\,</math> (nie udowodniono także przeciwnie - że <math>P=NP\,</math>), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście [[problemy milenijne|problemów milenijnych]]. Mimo ufundowania miliona dolarów za rozwiązanie problemu, nikomu się to nie udało.
|