BPL (complexidade)

Na teoria da complexidade computacional, BPL (Bounded-error Probabilistic Logarithmic-space, i.e. Espaço Logarítmico Probabilístico de Erro Limitado),[1] às vezes chamada de BPLP (Espaço Logarítmico Probabilístico de Erro Limitado e Tempo Polinomial),[2] é 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.[3] 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(log3/2 n) [4] e em L/poly.

References
  1. Complexity Zoo: BPL
  2. Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M. (1989), «Two applications of inductive counting for complementation problems», SIAM Journal on Computing, 18 (3): 559–578, doi:10.1137/0218038
  3. Nisan, N. (1994), «RL ⊆ SC», Computational Complexity, 4 (1): 1–11, doi:10.1007/BF01205052, An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing
  4. Complexity theory lecture notes
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.