PL (complexidade)

PL, ou L probabilístico, é a classe de linguagens reconhecíveis por uma máquina randômica de espaço logarítmico de tempo polinomial com probabilidade > 1/2 (chamado de erro ilimitado). De forma equivalente, como mostrado abaixo, PL é a classe de linguagens reconhecidas por máquinas randômizadas de tempo ilimitado e de espaço log com erro ilimitado.

Um exemplo de problema PL completo (sob redução logspace) é encontrar se o determinante de uma matriz (com coeficientes inteiros) é positivo. Dados uma matriz M e um número n, testar se |M| > n é também PL completo. Por outro lado, testar se o permanente de uma matriz é positiva é PP completo.

PL^PL=PL no sentido de que para cada f em PL, PL é inalterada se for alargada para  x→f(A,x) como uma subrotina, onde A é a string de entrada. PL contém NL e BPL , e está contida em NC2.

Aproximando o determinante em PL

O determinante de uma matriz de inteiros pode ser reduzida encontrando a diferença entre o número de caminhos de aceitação e rejeição em um grafo direcionado de tamanho polinomial com diferentes nós inicial, de aceitação e de rejeição.

A comparação do número de caminhos de aceitação e rejeição em PL é feita da seguinte forma. Modificando o grafo para fazer com que todos os caminhos tenham o mesmo tamanho e cada nó ter no máximo dois sucessores. Pegar um caminho aleatório. Para cada nó com somente um sucessor, falha (dê como saída uma resposta aleatória) com probabilidade 1/2. No final, aceita se estiver no nó de aceitação, rejeita se estiver no nó de rejeição, e falha em outro caso. Cada caminho distinto será contado igualmente - enquanto alguns caminhos estão mais propensos a serem excluídos, isto é exatamente compensado pela verossimilitude reduzida de continuar neste caminho.

Logspace probabilística sem limite de tempo

Se o tempo é ilimitado, é esperado que as máquinas rodem em tempo exponencial - por exemplo, ter um contador e incrementá-lo com a probabilidade de 1/2 e zero caso contrário; parar quando houver estouro no contador. Se zero erro (alternativamente, erro unilateral) for permitido, a classe é igual a NL - a máquina pode simular NL tentando caminhos aleatórios para uma quantidade de exponencial de tempo e usando NL = coNL.

Caso erro limitado seja permitido, uma problema de promessa completo ou problema de aproximação completo é estimar uma distribuição estacionária para uma cadeia de Markov ergótica (que volta ao estado experimentado anteriormente). A classe de complexidade não é conhecida como igual a PL, e é uma tentativa de simular PL no caso da probabilidade do teste da caixa preta falhar: Apesar do tempo ilimitado, o erros limitados em máquinas logspace não pode se distinguir uma entrada aleatória de uma cabeça que 1/2+1/s(n) onde s(n) cresce super polinomialmente.

Para máquinas logspace de erro ilimitado, tempo ilimitado pode ser reduzido a tempo polinomial da seguinte forma: Computar a probabilidade de aceitação poder ser reduzido para a resolução de um sistema linear. Para cada estado i, adicionar a variável x_i - probabilidade de aceitação se o atual estado é i. Se não existe caminho de i para Aceite, faça x_i = 0, caso contrário expresse x_i em termos de estados intermediários atingíveis a partir do estado i. O sistema pode ser resolvido usando determinantes, e testando se |A|>2|B| está em PL ('||' denota determinante). Uma complicação é que coeficientes estão em NL (usando NL = coNL). Lidamos com ela estipulando uma 'prova' para cada valor do coeficiente, falhando se o palpite não funcionar , e garantindo que todos os caminhos fazem o mesmo número de estipulações para cada coeficiente.