BPL (complexity)
Encyclopedia
In computational complexity theory
, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), is the complexity class
of problems solvable in logarithmic space and polynomial time with probabilistic Turing machine
s with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction.
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.
showed the weak derandomization result that BPL is contained in SC
. 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 DSPACE(log3/2 n)
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
of problems solvable in logarithmic space and polynomial time with probabilistic Turing machine
Probabilistic Turing machine
In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution....
s with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction.
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
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is 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
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
, the class PL is less practical because it may require a large number of rounds to reduce the error probability to a small constant.
showed the weak derandomization result that BPL is contained in SC
SC (complexity)
In computational complexity theory, SC is the complexity class of problems solvable by a deterministic Turing machine in polynomial time and polylogarithmic space...
. 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
NC (complexity)
In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...
and in DSPACE(log3/2 n)