Problem NP-zupełny: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
m Dodaję nagłówek przed Szablon:Przypisy |
Udowodnienie NP-zupełność=P nie zepsułoby RSA, ponieważ faktoryzacja liczb jest problemem NP, nie NP-zupełnym. Komuś się pomyliła NP-zupełność z NP-trudnością. |
||
Linia 4: | Linia 4: | ||
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 tak postawionego 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 tak postawionego problemu, nikomu się to nie udało. |
||
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 kryptosystemu [[RSA (kryptografia)|RSA]] (jednego z najbardziej popularnych szyfrów aktualnie stosowanych), gdyż opiera się on na założeniu, że problem podziału dowolnej liczby na czynniki pierwsze nie jest [[problem P|problemem wielomianowym]]. Problem ten jest w NP, ale nie udowodniono jego NP-trudności. |
|||
Problem nie może być jednocześnie NP-zupełny i [[Klasa Co-NPC|CoNP-zupełny]], chyba że <math>NP=CoNP</math>. |
Problem nie może być jednocześnie NP-zupełny i [[Klasa Co-NPC|CoNP-zupełny]], chyba że <math>NP=CoNP</math>. |
Wersja z 10:13, 23 sie 2018
Problem NP-zupełny (NPC, ang. NP-Complete) – problem zupełny w klasie NP, ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym[1]. 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 takim czasie 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 SAT, czyli problem spełnialności formuł zdaniowych. Udowodnił to w 1971 roku Stephen Cook.
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 tak postawionego problemu, nikomu się to nie udało.
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
- decyzyjna wersja problemu komiwojażera (COMI)
- pokrycie wierzchołkowe
- problem spełnialności (SAT)
- problem trójkolorowalności (3COL)
- kolorowanie grafu
- cykliczne pokrycie krawędziowe
- decyzyjna wersja problemu plecakowego
Zobacz też
- problem NP-trudny
- problem silnie NP-zupełny
- lista problemów NP-zupełnych
- problem NP-pośredni
- problem obliczeniowy
Przypisy
- ↑ Christos H Papadimitriou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 182,192. ISBN 83-204-2659-6.