BPP Class

In the theory of algorithms, the complexity class BPP (from the English bounded-error, probabilistic, polynomial ) is a class of predicates that are quickly (in polynomial time) computable and give an answer with a high probability (and by sacrificing time, you can achieve an arbitrarily high accuracy of the answer). Problems solved by probabilistic methods and lying in BPP arise in practice very often.

Content

Formal Definition

The class BPP is the class of predicates P (x) , computable on probabilistic Turing machines (ordinary Turing machines with a tape of random numbers) in polynomial time with an error of at most ⅓. This means that the probable Turing machine calculating the value of the predicate will give an answer in a time equal to O (n ^k ) , where n is the length x , and if the correct answer is 1, then the machine gives 1 with a probability of at least ⅔, and vice versa. The set of words in which P (x) returns 1 is called the language recognized by the predicate P (x) .

The number ⅓ in the definition is chosen arbitrarily: if instead of it we choose any number p strictly less than ½, then we get the same class. This is true, since if there is a Turing machine that recognizes a language with a probability of error p during the time O (n ^k ) , then the accuracy can be improved arbitrarily well due to the relatively small increase in time. If we start the machine n times in a row, and take the result of most starts as the result, then the probability of an error will drop to $\left(2{\sqrt {p(1-p)}}\right)^{n}$ ${\ displaystyle \ left (2 {\ sqrt {p (1-p)}} \ right) ^ {n}}$ , and the time becomes equal to O (n ^{k + 1} ) . Here, n machine starts are considered as a Bernoulli scheme with n tests and a 1-p probability of success, and the formula expressing an error is the probability of failure in at least half the cases. If you now start the machine n ² times in a row, then the time will increase to O (n ^{k + 2} ) , and the probability of error will drop to $\left(2{\sqrt {p(1-p)}}\right)^{n^{2}}$ ${\ displaystyle \ left (2 {\ sqrt {p (1-p)}} \ right) ^ {n ^ {2}}}$ . Thus, with an increase in the time polynomial exponent , the accuracy increases exponentially , and any desired value can be achieved.

Monte Carlo Algorithms

Probabilistic algorithm ${\mathcal {A}}$ ${\ displaystyle {\ mathcal {A}}}$ accepts language $L$ ${\ displaystyle L}$ according to the Monte Carlo standard, if the probability of an algorithm error does not exceed $1/3$ ${\ displaystyle 1/3}$ . I.e, $\mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3$ ${\ displaystyle \ mathbb {P} ({\ mathcal {A}} (x) = P (x)) \ geq 2/3}$ where $P(x)$ ${\ displaystyle P (x)}$ - word predicate $x$ ${\ displaystyle x}$ language $L$ ${\ displaystyle L}$ . Thus, the class BPP is formed by predicates such that for them there is a polynomial probabilistic algorithm that accepts their language according to the Monte Carlo standard. Such algorithms are also called Monte Carlo algorithms.

Relations with other classes

BPP itself is closed relative to the add-on. Class P is included in BPP because it provides a polynomial time response with zero error. BPP is included in the class $\Sigma _{2}^{p}\cap \Pi _{2}^{p}$ ${\ displaystyle \ Sigma _ {2} ^ {p} \ cap \ Pi _ {2} ^ {p}}$ polynomial hierarchy and, as a result, is included in PH and PSPACE . In addition, the inclusion of BPP in the P / Poly class is known.

The quantum analogue of the BPP class (in other words, the extension of the BPP class to quantum computers ) is the BQP class .

{\mbox{BPP}}\subseteq {\mbox{BQP}}

{\ displaystyle {\ mbox {BPP}} \ subseteq {\ mbox {BQP}}}

Other properties

Until 2002, one of the most well-known problems in the BPP class was the problem of recognizing prime numbers, for which there were several different polynomial probabilistic algorithms, such as the Miller-Rabin test , but not a single determinate one. However, in 2002, the deterministic polynomial algorithm was found by Indian mathematicians Agrawal, Kayan and Saxena, who thus proved that the problem of recognizing the prime number lies in the class P. The AKS algorithm they proposed (named after the first letters of their surnames) recognizes the simplicity of a number of length n over time O (n ⁴ ) .