Bounded-error Probabilistic Polynomial Time (BPP)
BPP is the
class of languages or decision problems solvable by a probabilistic Turing
machine that halts in polynomial time with the correct answer at least 2/3
of the time that is, with an error probability e of at most 1/3.
Since the choice of 1/3 is arbitrary, it can be any value
0 £ e < 1/2
without changing the problems in BPP. If the algorithm is run a polynomially
many times, the probability that most of the runs are yield a wrong answer is
exponentially small that is, by repeating the run, the probability of error may
be arbitrarily reduced.
If a
problem is in BPP, then there is an algorithm for it that is allowed to flip
coins, making random decisions, and that runs in polynomial time. It is known that
BPP = co-BPP. However, it is not
known if BPP í NP. For quantum computers the corresponding class is
BQP.
A
probabilistic Turing machine is a nondeterministic Turing machine where each
nondeterministic step is essentially a coin flip. Hence, each branch b of the probabilistic Turing machine
M1 has the probability Pr[b] = 2-k, where k is the number of coin flips for
branch b. So,
the probability that M1 accepts an input string w is Pr[M1(w) = 1] = ΠPr[b].
Considering
anomalous coin flips, we now account for errors. Turing machine M1
recognizes language L with error probability e if:
w ë L Þ Pr[M1(w) = 1] ³ 1 – e w ì L Þ Pr[M1(w) = 0] ³ 1 – e
Since the
error probability e, as mentioned above, may not suffice, we allow for
another BPP Turing machine M2 that operates with an error
probability of 2-poly(n). M2 takes M1 as
input, and runs it a polynomial number of times. As also alluded to above, this
will allow us to make the error probability exponentially small.
http://www.nist.gov/dads/HTML/bpp.html
http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-sixse4.html
http://encyclopedia.thefreedictionary.com/BPP
http://www.cse.msu.edu/~cse860/Lects/prob_algs.ppt