Kolejnym przykładem jest problem rozkładu podanej liczby na czynniki pierwsze. Istnieje dla tego problemu rozwiązanie kwantowe: probabilistyczny (algorytm Shora), jego praktyczna implementacja wymaga zbudowania komputera kwantowego. Brak możliwości efektywnego (obecne komputery kwantowe są zbyt słabe) rozkładu dużych liczb na czynniki pierwsze stanowi podstawę bezpieczeństwa większości algorytmów kryptografii asymetrycznej.
Istnieją wreszcie problemy NP-zupełne, dla których nie są znane efektywne algorytmy deterministyczne, probabilistyczne ani kwantowe (choć nie udowodniono, że nie istnieją). Problemy te są o tyle ważne, że obejmują większość istotnych praktycznych zagadnień występujących w przemyśle. Obecnie znane są jedynie sposoby efektywnego znajdowania przybliżonych rozwiązań i to tylko dla niektórych problemów tego typu.
W niektórych przypadkach problemem jest sama przewidywalność zachowania algorytmów deterministycznych. Przykładowo przy algorytmach kryptograficznych niezbędne jest, aby nikt z zewnątrz nie był w stanie zgadnąć zachowania algorytmu, który generuje klucze. Najczęściej realizowane jest to przy użyciu kryptograficznie bezpiecznych generatorów liczb pseudolosowych.
Przypisy
Kategoria:Algorytmika Kategoria:Teoria obliczeń