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

m
drobne merytoryczne
m (drobne merytoryczne)
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 [[Problemproblem NP-trudnyP|problemem trudnymwielomianowym]]. 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>.
146

edycji