52 Things: Number 7: How does randomness help in computation, and what is the class BPP?
Posted by Christopher Sherfield
This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This blog post concentrates on the Complexity Class BPP.
So far, during this blog series Ryan has introduced us to complexity classes, and in particular to P:
P is the class of languages decidable in polynomial time by a deterministic Turing machine.
Then, Guy introduced us to complexity class NP:
NP is the class of languages decidable in polynomial time by a nondeterministic Turing machine.
This week I am going to introduce the complexity class BPP:
BPP is the class of languages that are recognised by a probabilistic polynomial time Turing machine with an error probability of 1/3.
之前的两个知识点分别介绍了复杂类P问题和NP问题，一个是确定性图灵机DTM多项式时间可判定的，一个是非确定性图灵机NDTM多项式时间可判定的。这里介绍另一个复杂类BPP。在计算复杂度理论里面，BPP是在多项式时间内以概率图灵机解出的问题的集合, 并且对所有的输入，输出结果有错误的概率在1/3之内。BPP这个简写代表"Bounded-error"(有限错误)，"Probabilistic"(机率的)，"Polynomial time"(多项式时间)。
Probabilistic Turing Machine
A probabilistic Turing Machine  is a type of nondeterministic Turing Machine which randomly chooses between the available transitions at each point according to a probability distribution. What this means is that a probabilistic Turing machine can have stochastic results. On the same input, it could have different run times, accept it on one occasion and reject it on another. It could also never stop. This Turing Machine gives rise to other complexity classes such as RP, ZPP and, the one we're discussing in this post, BPP.
A little about the complexity class BPP
So as we have seen from the definition, the class BPP (Bounded-Error probabilistic polynomial time) contains the decision problems that are solvable in polynomial time by a probabilistic Turing machine with error probability 1/3. Note that this error probability can be chosen to be any value strictly between 0 and 1/2 due to a result named the amplification lemma which I will not discuss further here. The class BPP contains P, the class of problems solvable in polynomial time by a deterministic Turing Machine, this is due to the fact that a deterministic Turing Machine is a special case of the probabilistic Turing Machine (taking the only possible path with probability 1). As talked about in Guy's post, there is an open (Millennium) problem conjecturing as to whether P = NP. There is a similar question with BPP, being P = BPP? The number of problems known to be in BPP but not known to be in P is decreasing.
An example of a BPP Problem
One of the most famous problems known to be in BPP but not known to be in P was determining whether a number was prime. However, recently (2002) a deterministic polynomial time algorithm was found  for this problem meaning that it is indeed in P. Another problem known to be in BPP and currently still not known to be in P is polynomial identity testing , the problem of determining whether a polynomial is identically equal to the zero polynomial.
There are still many very important unanswered questions on the topic of Complexity Classes. Some of which, if answered, could have a large impact on shaping the future of Cryptography and Computer Science.
推荐您阅读更多有关于“ 52知识点 ”的文章请填写你的在线分享代码