RL (complejidad)
Espacio logarítmico aleatorio ( RL ), [1] a veces llamado RLP (tiempo polinomial de espacio logarítmico aleatorio), [2] es la clase de complejidad de los problemas de teoría de la complejidad computacional que se pueden resolver en el espacio logarítmico y el tiempo polinomial con máquinas de Turing probabilísticas con una error lateral . Se nombra en analogía con RP , que es similar pero no tiene restricción de espacio logarítmico.
Definición
Las máquinas probabilísticas de Turing en la definición de RL nunca aceptan incorrectamente, pero se les permite rechazar incorrectamente menos de 1/3 de las veces; esto se llama error unilateral . La constante 1/3 es arbitraria; cualquier x con 0 < x <1 sería suficiente. Este error se puede hacer 2 - p ( x ) veces más pequeño para cualquier polinomio p ( x ) sin usar más que el tiempo polinomial o el espacio logarítmico ejecutando el algoritmo repetidamente.
Relación con otras clases de complejidad
A veces, el nombre RL se reserva para la clase de problemas que pueden resolverse mediante máquinas probabilísticas de espacio logarítmico en tiempo ilimitado . Sin embargo, se puede demostrar que esta clase es igual a NL utilizando un contador probabilístico, por lo que generalmente se denomina NL en su lugar; esto también muestra que RL está contenido en NL . RL está contenido en BPL , que es similar pero permite error de dos caras (acepta incorrecto). RL contiene L , los problemas que pueden resolver las máquinas de Turing deterministas en el espacio logarítmico, ya que su definición es simplemente más general.
Noam Nisan mostró en 1992 el resultado de la desaleatorización débil de que RL está contenido en SC , [3] la clase de problemas que se pueden resolver en tiempo polinomial y espacio polilogarítmico en una máquina de Turing determinista; en otras palabras, dado el espacio polilogarítmico , una máquina determinista puede simular algoritmos probabilísticos del espacio logarítmico .
Se cree que RL es igual a L , es decir, que el cálculo del espacio logarítmico en tiempo polinómico puede desaleatorizarse por completo; La principal evidencia de esto fue presentada por Reingold et al. en 2005. [4] Una prueba de esto es el santo grial de los esfuerzos en el campo de la desaleatorización incondicional de las clases de complejidad. Un paso importante fue la prueba de Omer Reingold que SL es igual a L .
Referencias
- ^ Zoológico de complejidad : RL
- ^ A. Borodin, SA Cook, PW Dymond, WL Ruzzo y M. Tompa. Dos aplicaciones del conteo inductivo para problemas de complementación. SIAM Journal on Computing, 18 (3): 559–578. 1989.
- ^ Nisan, Noam (1992), "RL ⊆ SC", Actas del 24º Simposio de ACM sobre teoría de la computación (STOC '92) , Victoria, Columbia Británica, Canadá, págs. 619–623, doi : 10.1145 / 129712.129772.
- ^ O. Reingold y L. Trevisan y S. Vadhan. Caminatas pseudoaleatorias en gráficos birregulares y el problema RL vs. L, ECCC TR05-022 , 2004.
