
_START_ARTICLE_
BPP (複雜度)
_START_SECTION_
与其他复杂度类别的关系
_START_PARAGRAPH_
已知BPP 在取补集之下有封闭性; 换句话说, BPP=Co-BPP。 BPP是否是NP的子集仍旧是一个公开的问题。 另外NP是否是BPP的子集也是个公开的问题; 如果是的话，则NP=RP并且PH  BPP() (大多数人认为不会，因为这代表对一些很难的NP-完全 问题有着实际的解法)。现在已知RP是BPP的子集，并且BPP是PP的子集。 尚不清楚这两个是否为严格子集。 BPP包含在PH里面。因此之故，P=NP代表BPP=P，因为PH在这时会变成P。 _NEWLINE_存在特定够强的伪乱数产生器 是这领域里面大多数专家的猜想。这个猜想代表随机性并不给予多项式计算更多的能力：换句话说，P=RP=BPP。注意一般的产生器并不足以表示出结果；使用典型的乱数产生器实做的任何概率算法，与乱数的种子无关，对某一些特定的输入会一直给出错误的答案(即使这一些输入可能很稀少)。我们也可得到P = BPP ，若指数时间等级等同于E =  (Babai et al.),或者若E有指数的电路复杂性 (Impagliazzo and Wigderson)。 又BPP包含在i.o.-SUBEXP = 里面，若EXPTIME并不等同于MA (Babai et al.)._NEWLINE_一个Monte Carlo算法是一个"差不多正确"的随机算法。_NEWLINE_与跟它很像的拉斯维加斯算法比较，后者则是一个永远正确的随机算法，不过随机性在于有可能会回传推算失败。多项式时间之内的拉斯维加斯算法可以用来定义ZPP这个复杂度类。_NEWLINE_BPP包含在P/poly里面， 根据Adleman的理论，BPP是包含于P (复杂度)里面的。; 的确，根据这个事实证明的结果，每一个BPP的算法，只要输入是有限长度的话，我们可以借由一个决定性算法去找足够长的随机字串来消除BPP的随机特性。不过问题在于找到这个字串可能是很花费时间的事情。
_START_SECTION_
其他特性
_START_PARAGRAPH_
有很长一段时间, 一个非常有名的题目已知是BPP但不确定是否是P，是质数检测，也就是求一个给定的数字是否是质数。 然而,在2002年的论文 PRIMES is in P, Manindra Agrawal 与他的学生Neeraj Kayal 和 Nitin Saxena为了这个问题找到了一决定性，多项式时间的算法，因而证实这个问题是在P里面。_NEWLINE_一个很重要的范例问题已知在BPP内 (事实上在co-RP内)，但不知道是否在P之内。这问题是等同多项式检定, 这问题在于决定一个多项式是否完全等同于一个零多项式。 换句话说，是否存在任何变数数值的组合令这个多项式的结果不为零？ 这题目应均匀且随意的从一个至少d个值的有限集合取变数的值来达到有限机率的错误(d代表多项式的总次数)。_NEWLINE_BPP是低对应于自己, 代表一个能在常数时间内解决BPP问题的BPP机器 (一个BPP 启示图灵机) ，他的运算能力并不因此比没有这能力的机器更强(或说，两个不同机器定义出来的问题种类维持不变)。_NEWLINE_BPP这个语言集合是以一个普通的图灵机加上一个乱数的来源来定义。  相对应的量子计算机语言集合则是BQP。_NEWLINE_任何在BPP里面的语言可以被多项式大小的布林线路来决定(参见P/poly).