Problem NP-zupełny: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian |
m lit. |
||
Linia 9:
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
Problem nie może być jednocześnie '''NP-zupełny''' i [[Problem CoNP zupełny|CoNP-zupełny]], chyba że <math>NP=CoNP\,</math>.
| |||