Problem NP-zupełny: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m robot dodaje: sr:НП-комплетни проблеми |
m drobne merytoryczne |
||
Linia 5:
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 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 nie jest [[
Problem nie może być jednocześnie NP-zupełny i [[Problem CoNP zupełny|CoNP-zupełny]], chyba że <math>NP=CoNP\,</math>.
| |||