RP El tiempo polinómico aleatorio es la clase de complejidad de la teoría de la complejidad computacional, problemas para los que existe una máquina de Turing probabilística con estas propiedades: always Siempre se ejecuta en tiempo polinómico en el tamaño de entrada If Si la respuesta correcta es NO, siempre devuelve NO If Si la respuesta correcta es SÍ, entonces devuelve SÍ con una probabilidad de al menos 1/2.En otras palabras, al algoritmo se le permite lanzar una moneda verdaderamente aleatoria mientras se está ejecutando. El único caso en el que el algoritmo puede devolver SÍ es si la respuesta real es SÍ; por lo tanto, si el algoritmo termina y produce SÍ, entonces la respuesta correcta es definitivamente SÍ; sin embargo, el algoritmo puede terminar con NO independientemente de la respuesta real. Es decir, si el algoritmo devuelve NO, podría estar equivocado.Algunos autores llaman a esta clase R, aunque este nombre se usa más comúnmente para la clase de lenguajes recursivos.Si la respuesta correcta es SÍ y el algoritmo se ejecuta n veces con el resultado de cada ejecución estadísticamente independiente de las otras, entonces devolverá SÍ al menos una vez con una probabilidad de al menos 1 − 2−. Así que si el algoritmo se ejecuta 100 veces, entonces la probabilidad de que dé la respuesta incorrecta cada vez es menor que la probabilidad de que los rayos cósmicos corrompan la memoria de la computadora que ejecuta el algoritmo. En este sentido, si una fuente de números aleatorios está disponible, la mayoría de los algoritmos en RP son altamente prácticos.

ver más «