# Difference between revisions of "The complexity class BPP"

A slightly more formal definition is the following. A Boolean function $f:\bigcup_{n=1}^\infty\{0,1\}^n\rightarrow\{0,1\}$ belongs to BPP if there is a randomized polynomial-time algorithm such that for any x such that f(x)=1 it will output 1 with probability at least 2/3, and for any x such that f(x)=0 it will output 0 with probability at least 2/3. This may not sound like "almost always" getting the right answer, but a standard trick allows you to get the almost always from such an algorithm: you just run it several times. If there is a probability of 2/3 of getting the answer right, then almost certainly you will get the answer right over half the time if you run the algorithm (independently) 50 times, say. Indeed, the probability that this is not the case decreases exponentially with the number of times you repeat the algorithm.