Un ejemplo de algoritmo con esta clase de complejidad es el Test de Solovay-Strassen que permite determinar si un número es primo o compuesto. El algoritmo tiene tiempo polinomial sobre la magnitud de la entrada. El algoritmo se basa en que si el número m de entrada es primo, entonces la salida es primo, pero si m es compuesto, la salida puede ser primo con probabilidad a lo más un medio. El algoritmo puede ser repetido cualquier número de veces con resultados independientes. Así, si la respuesta alguna vez es compuesto, sabemos que es compuesto, mientras que si la respuesta es siempre primo, después de un número i de veces, entonces podemos decir sin apenas riesgo de equivocarnos que es primo, dado que fijado un compuesto cualquiera m, la probabilidad de que se diera ese resultado es menor que 
[2]
Otro ejemplo es el algoritmo Berlekamp, para factorizar un polinomio f sobre el cuerpo de los campos de Galois.[2]
