Problem NP-zupełny: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
wykazano wykazano |
==Przykłady== |
||
Linia 7: | Linia 7: | ||
Pytanie związane z problemami NP-zupełnymi ma szczególne znaczenie w [[kryptografia|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 (kryptografia)|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 [[Problem NP-trudny|problemem trudnym]]. Problem ten jest w NP, ale nie udowodniono jego NP-trudności. |
Pytanie związane z problemami NP-zupełnymi ma szczególne znaczenie w [[kryptografia|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 (kryptografia)|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 [[Problem NP-trudny|problemem trudnym]]. Problem ten jest w NP, ale nie udowodniono jego NP-trudności. |
||
Problem nie może być jednocześnie |
Problem nie może być jednocześnie NP-zupełny i [[Problem CoNP zupełny|CoNP-zupełny]], chyba że <math>NP=CoNP\,</math>. |
||
==Przykłady== |
|||
Przykłady problemów NP-zupełnych: |
Przykłady problemów NP-zupełnych: |
||
*[[cykl Hamiltona|problem cyklu Hamiltona]] |
*[[cykl Hamiltona|problem cyklu Hamiltona]] |
Wersja z 15:08, 5 cze 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. 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 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
Przykłady problemów NP-zupełnych:
- problem cyklu Hamiltona
- problem kliki
- problem komiwojażera (COMI)
- pokrycie wierzchołkowe
- problem plecakowy
- problem spełnialności (SAT)
- problem trójkolorowalności (3COL)
- kolorowanie grafu
- cykliczne pokrycie krawędziowe