PL (complejidad)

PL , o L probabilístico , es la clase de lenguajes reconocibles por una máquina aleatoria de espacio logarítmico y tiempo polinomial con probabilidad > 1/2 (esto se denomina error ilimitado). De forma equivalente, como se muestra a continuación, PL es la clase de lenguajes reconocidos por una máquina aleatoria de espacio logarítmico y tiempo ilimitado con error ilimitado. 

Un ejemplo de problema PL completo (bajo reducción de espacio logarítmico) es encontrar si el determinante de una matriz (con coeficientes enteros) es positivo. Dada una matriz M y un número n , probar con${\displaystyle |M|>n}$^{[ nota 1 ]} también es PL completo. Por el contrario, probar si elpermanentees positivo esPPcompleto.

PL ^PL =PL en el sentido de que para cada f en PL, PL no cambia si se extiende para permitir ⁠${\displaystyle x\to f(A,x)}$como una subrutina, donde A es la cadena de entrada.

PL contiene NL y BPL y está contenido en NC ₂ .

El determinante de una matriz integral se puede reducir a encontrar la diferencia entre el número de caminos de aceptación y rechazo en un grafo acíclico dirigido de tamaño polinomial con nodos de inicio, aceptación y rechazo distinguidos. ^{[ 1 ]}

Comparar el número de caminos de aceptación y rechazo se puede hacer en PL de la siguiente manera. Modificar el grafo para que todos los caminos tengan la misma longitud y que cada nodo tenga como máximo dos sucesores. Tomar un camino aleatorio. Para cada nodo con un solo sucesor, fallar (mostrar una respuesta aleatoria) con una probabilidad de 1/2 . Al final, aceptar si llegamos al nodo de aceptación, rechazar si llegamos al nodo de rechazo y fallar en caso contrario. Cada camino distinto se contará por igual ; si bien algunos caminos tienen más probabilidades de ser tomados, esto se compensa exactamente con una menor probabilidad de continuar por ese camino.

Si el tiempo es ilimitado, las máquinas pueden funcionar en un tiempo exponencial esperado ; por ejemplo, mantener un contador e incrementarlo con probabilidad 1/2 y ponerlo a cero en caso contrario; detenerse cuando el contador se desborde. Si se permite un error cero (o un error unilateral), la clase es igual a NL ; la máquina puede simular NL probando rutas aleatorias durante un tiempo exponencial y usando NL=coNL.

Si se permite un error acotado, un problema completo de promesa o aproximación es estimar la distribución estacionaria para una cadena de Markov ergódica . No se sabe si la clase de complejidad es igual a PL, y un intento de simular PL a través de la amplificación de probabilidad de caja negra falla: a pesar del tiempo ilimitado, las máquinas de espacio logarítmico de error acotado no pueden distinguir una moneda aleatoria de una que cae cara .${\displaystyle 1/2+1/s(n)}$del tiempo donde${\displaystyle s(n)}$Crece de forma superpolinómica.

Para máquinas de espacio logarítmico de error no acotado, el tiempo no acotado se puede reducir a tiempo polinomial de la siguiente manera. El cálculo de la probabilidad de aceptación se puede reducir a la resolución de un sistema lineal. Para cada estado i , agregue una variable x _i — probabilidad de aceptación si el estado actual es i. Si no hay un camino de i a Aceptar , establezca x _i = 0 , y de lo contrario exprese x _i en términos de estados inmediatamente alcanzables desde el estado i. El sistema se puede resolver usando determinantes y probando si${\displaystyle |A|>2|B|}$está en PL. ^{[ nota 1 ]} Una complicación es que los coeficientes están en NL (usando NL=coNL). Lo solucionamos adivinando una "prueba" para cada valor de coeficiente, fallando si la suposición no funciona, y asegurándonos de que todos los caminos hagan el mismo número de suposiciones para cada coeficiente.