# 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 if you run the algorithm repeatedly and take a majority vote to determine the answer, the chance of making an error decreases exponentially with the number of times the algorithm is run.