En la teoría de la complejidad computacional , BPL (espacio logarítmico probabilístico de error acotado), [1] a veces llamado BPLP (tiempo polinomial de espacio logarítmico probabilístico de error acotado ), [2] es la clase de complejidad de problemas que se pueden resolver en espacio logarítmico y polinomio tiempo con máquinas probabilísticas de Turing con error de dos caras . Se nombra en analogía con BPP , que es similar pero no tiene restricción de espacio logarítmico.
Modelo de error
Las máquinas probabilísticas de Turing en la definición de BPL solo pueden aceptar o rechazar incorrectamente menos de 1/3 de las veces; esto se llama error de dos caras . La constante 1/3 es arbitraria; cualquier x con 0 ≤ x <1/2 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.
Clases relacionadas
Dado que el error bilateral es más general que el error unilateral, RL y su complemento co-RL están contenidos en BPL . BPL también está contenido en PL , que es similar excepto que el límite de error es 1/2, en lugar de una constante menor que 1/2; como la clase PP , la clase PL es menos práctica porque puede requerir un gran número de rondas para reducir la probabilidad de error a una pequeña constante.
Nisan (1994) mostró el débil resultado de la desaleatorización de que BPL está contenido en SC . [3] SC es 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, este resultado muestra que, dado el espacio polilogarítmico , una máquina determinista puede simular algoritmos probabilísticos del espacio logarítmico .
BPL está contenido en NC y en L / poly . Saks y Zhou demostraron que BPL está contenido en DSPACE (log 3/2 n), [4] y en 2021 Hoza mejoró esto para mostrar que BPL está contenido en DSPACE . [5]
Referencias
- ^ "Complejidad Zoo: BPL" . Archivado desde el original el 5 de agosto de 2012 . Consultado el 4 de octubre de 2011 .
- ^ Borodin, A .; Cook, SA ; Dymond, PW; Ruzzo, WL; Tompa, M. (1989), "Dos aplicaciones del conteo inductivo para problemas de complementación", SIAM Journal on Computing , 18 (3): 559–578, CiteSeerX 10.1.1.394.1662 , doi : 10.1137 / 0218038
- ^ Nisan, N. (1994), "RL ⊆ SC", Computational Complexity , 4 (1): 1–11, doi : 10.1007 / BF01205052 , Una versión anterior de este artículo apareció en el Simposio de Teoría de la Computación de 1992
- ^ Notas de la conferencia de teoría de la complejidad
- ^ [1]