BPL (Bounded-error Probabilistic Logarithmic-space) is a complexity class in computational complexity theory. It represents the set of decision problems solvable by a probabilistic Turing machine that operates in logarithmic space, has two-sided bounded error, and runs in polynomial time.
Specifically, a decision problem is in BPL if there exists a probabilistic Turing machine M satisfying the following conditions:
- Space Complexity: M uses O(log n) space, where n is the size of the input.
- Time Complexity: M runs in polynomial time.
- Bounded Error:
- If the correct answer is "yes", then M accepts with probability at least 2/3.
- If the correct answer is "no", then M accepts with probability at most 1/3.
The constants 2/3 and 1/3 in the bounded error condition are arbitrary and can be replaced with any constants a and b such that 1/2 < a < 1 and b = 1-a, without changing the class. This is due to amplification techniques that can boost the probability of correctness.
BPL is known to be contained within other complexity classes, such as L (deterministic logarithmic space) and RL (randomized logarithmic space with one-sided error). Determining the precise relationship between BPL, L, and RL is an open problem in complexity theory. It is known that L ⊆ BPL ⊆ RL.
Problems in BPL can be thought of as being efficiently solvable in logarithmic space with a high degree of confidence, even with access to randomness.
The study of BPL and related complexity classes helps researchers understand the power of randomness in computation when resources are constrained.