Surf Wiki
Save to docs
general/probabilistic-complexity-classes

From Surf Wiki (app.surf) — the open knowledge base

BPL (complexity)

Concept in computational complexity theory

Summary

Concept in computational complexity theory

In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time),{{citation

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 −p(x) times smaller for any polynomial p(x) without using more than polynomial time or logarithmic space by running the algorithm repeatedly.

References

References

  1. "Complexity Zoo: BPL".
  2. [http://pages.cs.wisc.edu/~dieter/Courses/2007s-CS810/Scribes/PS/lecture11.ps Complexity theory lecture notes]
  3. (2021). "Better Pseudodistributions and Derandomization for Space-Bounded Computation".
Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

probabilistic-complexity-classes
Want to explore this topic further?

Ask Mako anything about BPL (complexity) — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report