PL (complejidad)
PL , o L probabilística , es la clase de lenguajes reconocibles por una máquina aleatoria de espacio logarítmico de tiempo polinomial con probabilidad > 1 ⁄ 2 (esto se llama error ilimitado). De manera equivalente, como se muestra a continuación, PL es la clase de lenguajes reconocidos por una máquina aleatoria de espacio de registro de error ilimitado de tiempo ilimitado.
Un ejemplo de problema completo PL (bajo reducción de espacio logarítmico) es encontrar si el determinante de una matriz (con coeficientes integrales) es positivo. Dada una matriz M y un número n , la prueba con [nota 1] también es PL completa. Por el contrario, probar si la matriz permanente es positiva es PP completo.
PL PL =PL en el sentido de que para cada f en PL, PL no cambia si se extiende para permitir como una subrutina, donde A es la cadena de entrada.
El determinante de una matriz integral se puede reducir a encontrar la diferencia entre el número de rutas de aceptación y rechazo en un gráfico acíclico dirigido de tamaño polinomial con nodos de inicio, aceptación y rechazo distinguidos.[1]
La comparación del número de rutas de aceptación y rechazo se puede realizar en PL de la siguiente manera. Modifique el gráfico para que todos los caminos tengan la misma longitud y para que cada nodo tenga como máximo dos sucesores. Toma un camino aleatorio. Para cada nodo con solo un sucesor, falle (respuesta aleatoria de salida) con probabilidad 1 ⁄ 2 . Al final, aceptar si llegamos al nodo Aceptar, rechazar si llegamos al nodo Rechazar y fallar en caso contrario. Cada camino distinto se contará por igual, aunque es más probable que se tomen algunos caminos, esto se compensa exactamente con la probabilidad reducida de continuar por ese camino.
Si el tiempo es ilimitado, las máquinas pueden funcionar en el tiempo exponencial esperado; por ejemplo, mantener un contador e incrementarlo con una probabilidad de 1 ⁄ 2 y ponerlo a cero de lo contrario; detenerse cuando el contador se desborda. Si se permite un error cero (alternativamente, un error unilateral), la clase es igual a NL: la máquina puede simular NL probando rutas aleatorias durante una cantidad de tiempo exponencial y usando NL=coNL.