BPP (复杂度)
在计算复杂度理论里面，BPP是在多项式时间内以机率图灵机解出的问题的集合, 并且对所有的输入，输出结果有错误的概率在1/3之内。BPP这个简写代表"Bounded-error"(有限错误)，"Probabilistic"(机率的)，"Polynomial time"(多项式时间)。
| BPP 演算法 (操作一次) | ||
|---|---|---|
| 产生的答案 | ||
| 正确 解答 |
是 | 否 |
| 是 | ≥ 2/3 | ≤ 1/3 |
| 否 | ≤ 1/3 | ≥ 2/3 |
| BPP 演算法 (操作k次) | ||
| 产生的答案 | ||
| 正确 解答 |
是 | 否 |
| 是 | > 1 − 2−ck | < 2−ck |
| 否 | < 2−ck | > 1 − 2−ck |
| 对于某些常数 c > 0 | ||
要是一个问题在BPP集合里面，则存在一个演算法，此演算法允许转硬币作随机的决定，并在多项式时间内结束。 对这个演算法的任何输入，他都要在小于1/3的错误概率之下给出正确判断，不论这一个问题的答案是"正确"或者"错误"。
在这里定义里面的1/3是任意给定的。它可以是在 0 与 1/2(不包含0与1/2自身) 之间的 任意常数而BPP集合维持不变(当然这个常数必须跟输入值为何无关)。原因在于，虽然这演算法有错误的机率，但是只要我们多进行几次演算法，那多数的答案都是错误的机率会呈现指数衰减 [1]（页面存档备份，存于互联网档案馆）. 因此证明我们可以很简单的架构一个更准确的演算法，仅仅单纯多重复几次这个演算法然后对每次的答案作多数决。
BPP是大小最大的几个实际的问题类别之一，代表大多数的BPP问题都有有效率的概率演算法，因此以上倏地方法可以用现在的机器快速取得解答。因为这个原因，我们对哪一些问题或问题种类在BPP里面有著实用方面的兴趣。
定义
[编辑]一个语言L在BPP里面，若且唯若这语言存在一个概率图灵机 M，另
- M对任何输入均在多项式时间后停止
- 对任何字串x在L之内, 对M输入x之后，M 输出 1 的机率大于或者等于 2/3
- 对任何字串 x 不在 L之内, 对M输入x之后，M 输出 1 的机率小于或者等于 1/3
另外，BPP可以仅以决定性图灵机定义。一个语言L是在BPP里面若且唯若存在一个多项式p和一个决定性图灵机M，满足
- M对任何输入均操作多项式时间之内
- 对任何字串x在L之内, 对长度为 p(|x|)的任意字串y ，满足 M(x,y) = 1 这条件的机率超过或等于2/3
- 对任何字串 x 不在 L之内, 对长度为 p(|x|)的任意字串 y ，满足 M(x,y) = 1 这条件的机率小于或等于1/3
与其他复杂度类别的关系
[编辑]已知 BPP 在取补集之下有封闭性; 换句话说, BPP=Co-BPP。 BPP是否是NP的子集仍旧是一个公开的问题。 另外NP是否是BPP的子集也是个公开的问题; 如果是的话，则NP=RP并且PH BPP([2]) (大多数人认为不会，因为这代表对一些很难的NP-完全 问题有著实际的解法)。现在已知RP是BPP的子集，并且BPP是PP的子集。 尚不清楚这两个是否为严格子集。 BPP包含在PH里面。因此之故，P=NP代表BPP=P，因为PH在这时会变成P。 存在特定够强的伪乱数产生器 是这领域里面大多数专家的猜想。这个猜想代表随机性并不给予多项式计算更多的能力：换句话说，P=RP=BPP。注意一般的产生器并不足以表示出结果；使用典型的乱数产生器实做的任何概率演算法，与乱数的种子无关，对某一些特定的输入会一直给出错误的答案(即使这一些输入可能很稀少)。我们也可得到P = BPP ，若指数时间等级等同于E = (Babai et al.),或者若E有指数的电路复杂性 (Impagliazzo and Wigderson)。 又BPP包含在i.o.-SUBEXP = 里面，若EXPTIME并不等同于MA (Babai et al.).
一个Monte Carlo演算法是一个"差不多正确"的随机演算法。 与跟它很像的拉斯维加斯演算法比较，后者则是一个永远正确的随机演算法，不过随机性在于有可能会回传推算失败。多项式时间之内的拉斯维加斯演算法可以用来定义ZPP这个复杂度类。
BPP包含在P/poly里面， 根据Adleman的理论，BPP是包含于P (复杂度)里面的。[1]; 的确，根据这个事实证明的结果，每一个BPP的演算法，只要输入是有限长度的话，我们可以借由一个决定性演算法去找足够长的随机字串来消除BPP的随机特性。不过问题在于找到这个字串可能是很花费时间的事情。
其他特性
[编辑]有很长一段时间, 一个非常有名的题目已知是BPP但不确定是否是P，是质数检测，也就是求一个给定的数字是否是质数。 然而,在2002年的论文 PRIMES is in P, Manindra Agrawal 与他的学生 Neeraj Kayal 和 Nitin Saxena为了这个问题找到了一决定性，多项式时间的演算法，因而证实这个问题是在P里面。
一个很重要的范例问题已知在BPP内 (事实上在co-RP内)，但不知道是否在P之内。这问题是等同多项式检定, 这问题在于决定一个多项式是否完全等同于一个零多项式。 换句话说，是否存在任何变数数值的组合令这个多项式的结果不为零？ 这题目应均匀且随意的从一个至少 d个值的有限集合取变数的值来达到有限机率的错误(d代表多项式的总次数)。[2]
BPP是低对应于自己 , 代表一个能在常数时间内解决BPP问题的BPP机器 (一个BPP 启示图灵机) ，他的运算能力并不因此比没有这能力的机器更强(或说，两个不同机器定义出来的问题种类维持不变)。
BPP这个语言集合是以一个普通的图灵机加上一个乱数的来源来定义。 相对应的量子计算机语言集合则是BQP。
任何在BPP里面的语言可以被多项式大小的布林线路来决定 (参见P/poly).[3]
参考资料
[编辑]- ^ Adleman, L. M. Two theorems on random polynomial time. Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing: 75–83. 1978.
- ^ Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP. February 26, 2003. http://people.csail.mit.edu/madhu/ST03/scribe/lect06.pdf （页面存档备份，存于互联网档案馆）
- ^ Leonard Adleman, Two theorems on random polynomial time, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing, 1978, pp. 75–83.
- László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity, 3:307–318.
- Russell Impagliazzo and Avi Wigderson (1997). "P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. doi:10.1145/258533.258590
- Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". Simon Fraser University.
- Christos Papadimitriou. Computational Complexity 1st edition. Addison Wesley. 1993. ISBN 0-201-53082-1. Pages 257–259 of section 11.3: Random Sources. Pages 269–271 of section 11.4: Circuit complexity.
- Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Section 10.2.1: The class BPP, pp.336–339.
