RL (complejidad)

El espacio logarítmico aleatorio ( RL ), ^{[ 1 ]} a veces llamado RLP (espacio logarítmico aleatorio de tiempo polinomial), ^{[ 2 ]} es la clase de complejidad de los problemas de la teoría de la complejidad computacional que se pueden resolver en espacio logarítmico y tiempo polinomial con máquinas de Turing probabilísticas con error unilateral . Se denomina así por analogía con RP , que es similar pero no tiene la restricción del espacio logarítmico.

Los algoritmos de aprendizaje por refuerzo (RL) nunca aceptan incorrectamente, pero se les permite rechazar incorrectamente menos de 1/3 de las veces; esto se denomina error unilateral . La constante 1/3 es arbitraria; cualquier x con 0 < x < 1 sería suficiente. Este error puede reducirse 2 ^{− p ( x )} veces para cualquier polinomio p ( x ) sin utilizar más que tiempo polinomial o espacio logarítmico ejecutando el algoritmo repetidamente.

A veces, el nombre RL se reserva para la clase de problemas que pueden ser resueltos por máquinas probabilísticas en espacio logarítmico en tiempo ilimitado . Sin embargo, se puede demostrar que esta clase es igual a NL usando un contador probabilístico, por lo que generalmente se la denomina NL ; esto también demuestra que RL está contenida en NL . RL está contenida en BPL , que es similar pero permite errores bilaterales (aceptaciones incorrectas). RL contiene L , los problemas que pueden ser resueltos por máquinas de Turing deterministas en espacio logarítmico, ya que su definición es simplemente más general.

Noam Nisan demostró en 1992 el resultado de desaleatorización débil de que RL está contenido en SC , ^{[ 3 ]} la clase de problemas resolubles en tiempo polinomial y espacio polilogarítmico en una máquina de Turing determinista; en otras palabras, dado un espacio polilogarítmico , una máquina determinista puede simular algoritmos probabilísticos en espacio logarítmico .

Se cree que RL es igual a L , es decir, que el cálculo del espacio logarítmico en tiempo polinomial puede ser completamente desaleatorizado; Reingold et al. presentaron evidencia importante de esto en 2005. ^{[ 4 ]} Una prueba de esto es el santo grial de los esfuerzos en el campo de la desaleatorización incondicional de clases de complejidad. Un paso importante hacia adelante fue la prueba de Omer Reingold de que SL es igual a L.