Problemy, dla których istnieją algorytmy probabilistyczne działające średnio w czasie wielomianowym, ale potencjalnie o dowolnie długim czasie działania, tworzą klasę ZPP.
Derandomizacja Algorytmy probabilistyczne są zwykle prostsze i efektywniejsze od algorytmów deterministycznych dla tych samych problemów. Usuwanie wymagania losowości z algorytmów i tworzenie w ten sposób równie silnych algorytmów deterministycznych jest obecnie bardzo aktywnym obszarem badań.
Zobacz też Test Millera-Rabina Sortowanie szybkie Algorytm deterministyczny
Kategoria:Algorytmika Kategoria:Teoria obliczeń Kategoria:Rachunek prawdopodobieństwa