BPL (complejidad)

En la teoría de la complejidad computacional , BPL (Bounded-error Probabilistic Logarithmic-space), ^{[ 1 ]} a veces llamado BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), ^{[ 2 ]} es la clase de complejidad de problemas resolubles en espacio logarítmico y tiempo polinomial con máquinas de Turing probabilísticas con error bilateral . Se nombra por analogía con BPP , que es similar pero no tiene la restricción de espacio logarítmico.

Las máquinas de Turing probabilísticas en la definición de BPL solo pueden aceptar o rechazar incorrectamente menos de 1/3 de las veces; esto se denomina error bilateral . La constante 1/3 es arbitraria; cualquier x con 0 ≤ x < 1/2 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.

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; al igual que la clase PP , la clase PL es menos práctica porque puede requerir una gran cantidad de rondas para reducir la probabilidad de error a una pequeña constante.

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

BPL está contenido en NC y en L/poli . Saks y Zhou demostraron que BPL está contenido en DSPACE (log ^3/2 n), ^{[ 4 ]} y en 2021 Hoza mejoró esto para demostrar que BPL está contenido en DSPACE . ^{[ 5 ]}${\displaystyle (\log ^{3/2}(n)/{\sqrt {\log \log n}})}$