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

Dodane 9 bajtów ,  14 lat temu
==Przykłady==
(wykazano wykazano)
(==Przykłady==)
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 '''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:
*[[cykl Hamiltona|problem cyklu Hamiltona]]
46 437

edycji