Son algoritmos que resuelven un problema P utilizando como parámetro extra una cadena aleatoria “r”. Realiza decisiones de ejecución teniendo en cuenta la lectura de la cadena aleatoria (elecciones aleatorias). Es debido a estas diferentes ejecuciones de la misma instancia que puede ejecutarse en diferente cantidad de pasos o retornar una salida diferente.
Permiten construir soluciones “simples” de implementar y entender, además de hallar soluciones más rápido que algoritmos conocidos (con la posibilidad de fallar en el intento o en el tiempo que toman para ejecutarse).
Dan resultados probablemente correctos, se espera que esta probabilidad sea grande. Se ejecutan en tiempo polinomial. Sabemos su cota de complejidad pero no si el resultado obtenido es el óptimo (aunque sí sabemos que hay una probabilidad de que lo sea).
Dan resultados correctos (el óptimo) pero se ejecutan “probablemente rápido”, se espera que su tiempo de ejecución sea rápido. No tienen acotado al tiempo de ejecución (no terminan hasta hallar el resultado correcto).
Son aquellos problemas de decisión para los que existe un programa M randomizado que se ejecuta en tiempo polinomial tal que para toda instancia I del problema:
Son aquellos problemas de decisión para los que existe un programa M randomizado que se ejecuta en tiempo polinomial tal que para toda instancia I del problema:
Son aquellos problemas de decisión que pertenecen a la intersección entre RP y co-RP. Para toda instancia I del problema podemos ejecutar tanto un algoritmo en RP como en co-RP. En tiempo polinomial tendremos entonces tres respuestas posibles (si, no y no sé). La repetición de un número no determinado de ejecuciones nos asegura obtener el resultado correcto (corresponden a los algoritmos conocidos como “Las Vegas”).
