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

Z Wikipedii, wolnej encyklopedii
[wersja nieprzejrzana][wersja nieprzejrzana]
Usunięta treść Dodana treść
Stv.bot (dyskusja | edycje)
m robot poprawia: nl:NP-volledig
Ksoltys (dyskusja | edycje)
styl
Linia 1: Linia 1:
'''Problem NP-zupełny''' (NPC) to problem, który należy do klasy [[Problem NP|NP]] oraz jest [[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).
'''Problemy NP-zupełne''' (NPC) to takie problemy klasy [[Problem NP|NP]], że każdy inny problem klasy [[Problem NP|NP]]
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.


Pierwszym problemem, którego wykazano NP-zupełność wykazano, był problem 3-[[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.
Problemy NP-zupełne można traktować jako najtrudniejsze problemy klasy NP
(z punktu widzenia wielomianowej rozwiązywalności).

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.


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.
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.

Wersja z 19:58, 27 kwi 2007

Problem NP-zupełny (NPC) to problem, który należy do klasy NP oraz jest 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-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.

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ż (nie udowodniono także przeciwnie - że ), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście problemów milenijnych. Mimo ufundowania miliona dolarów za rozwiązanie problemu, nikomu się to nie udało.

Pytanie związane z problemami NP-zupełnymi ma szczególne znaczenie w kryptografii - rozwiązanie któregokolwiek problemu NP-zupełnego w czasie wielomianowym (a zatem rozwiązanie ich wszystkich) umożliwiłoby między innymi szybkie łamanie szyfru RSA (jednego z najbardziej popularnych szyfrów aktualnie stosowanych) - opiera się on na założeniu, że problem podziału dowolnej liczby na czynniki pierwsze jest problemem trudnym. Problem ten jest w NP, ale nie udowodniono jego NP-trudności.

Problem nie może być jednocześnie NP-zupełny i CoNP-zupełny, chyba że .

Przykłady problemów NP-zupełnych:

Zobacz też