BPL (complexity)

Last updated

In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), [1] sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), [2] is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error. It is named in analogy with BPP , which is similar but has no logarithmic space restriction.

Contents

Error model

The probabilistic Turing machines in the definition of BPL may only accept or reject incorrectly less than 1/3 of the time; this is called two-sided error. The constant 1/3 is arbitrary; any x with 0 ≤ x < 1/2 would suffice. This error can be made 2−p(x) times smaller for any polynomial p(x) without using more than polynomial time or logarithmic space by running the algorithm repeatedly.

Since two-sided error is more general than one-sided error, RL and its complement co-RL are contained in BPL. BPL is also contained in PL , which is similar except that the error bound is 1/2, instead of a constant less than 1/2; like the class PP , the class PL is less practical because it may require a large number of rounds to reduce the error probability to a small constant.

Nisan (1994) showed the weak derandomization result that BPL is contained in SC . [3] SC is the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, this result shows that, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms.

BPL is contained in NC and in L/poly . Saks and Zhou showed that BPL is contained in DSPACE(log3/2 n), [4] and in 2021 Hoza improved this to show BPL is contained in DSPACE. [5]

References

  1. ↑ "Complexity Zoo: BPL". Archived from the original on 2012-08-05. Retrieved 2011-10-04.
  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, CiteSeerX   10.1.1.394.1662 , 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
  5. ↑ Hoza, William (2021). "Better Pseudodistributions and Derandomization for Space-Bounded Computation".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.