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

Usunięte 583 bajty ,  3 lata temu
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ą.
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ą.)
 
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>.
1

edycja