BPL (complexidade)

Na teoria da complexidade computacional, BPL (Bounded-error Probabilistic Logarithmic-space, i.e. Espaço Logarítmico Probabilístico de Erro Limitado), às vezes chamada de BPLP (Espaço Logarítmico Probabilístico de Erro Limitado e Tempo Polinomial), é a classe de complexidade dos problemas solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro bilateral. É assim denominado, em analogia com o BPP, que é semelhante, mas não tem restrição de espaço logarítmico.

As máquinas de Turing probabilísticas na definição de BPL podem apenas aceitar ou rejeitar incorretamente menos de 1/3 das vezes; isto é chamado de erro bilateral. A constante de 1/3 é arbitrária; qualquer x , com 0 ≤ x < 1/2 seria suficiente. Este erro pode ser reduzido em 2^−p(x) vezes para qualquer polinômio p(x) sem utilizar mais do que um tempo polinomial ou espaço logarítmico ao se executar o algoritmo várias vezes.

Já que erro bilateral é mais geral que o erro unilateral, RL e seu complemento co-RL estão contidos em BPL, BPL também está em PL, o que é similar, exceto que o limite do erro é 1/2 ao invés de uma constante a menos que 1/2; assim como a classe PP, a classe PL é menos prática pois pode precisar de uma grande quantidade de iterações para reduzir a probabilidade de erro a uma pequena constante.

Nisan (1994) mostrou o resultado fraco da desrandomização de que BPL está contida em SC. SC é a classe de problemas solúveis em tempo polinomial e espaço logarítmico numa máquina de Turing determinística; em outras palavras, este resultado mostra que dado um espaço polilogaritmico, uma máquina determinística consegue simular algoritmos probabilísticos de espaço logarítmico.

BPL está contida em NC e em DSPACE(log^3/2 n) e em L/poly.