BPP (复杂度)

计算复杂度理论里面,BPP是在多项式时间内以几率图灵机解出的问题的集合, 并且对所有的输入,输出结果有错误的概率在1/3之内。BPP这个简写代表"Bounded-error"(有限错误),"Probabilistic"(几率的),"Polynomial time"(多项式时间)。

BPP 算法 (操作一次)
产生的答案
正确
解答
≥ 2/3 ≤ 1/3
≤ 1/3 ≥ 2/3
BPP 算法 (操作k次)
产生的答案
正确
解答
> 1 − 2ck < 2ck
< 2ck > 1 − 2ck
对于某些常数 c > 0

要是一个问题在BPP集合里面,则存在一个算法,此算法允许转硬币作随机的决定,并在多项式时间内结束。 对这个算法的任何输入,他都要在小于1/3的错误概率之下给出正确判断,不论这一个问题的答案是"正确"或者"错误"。

在这里定义里面的1/3是任意给定的。它可以是在 0 与 1/2(不包含0与1/2自身) 之间的 任意常数而BPP集合维持不变(当然这个常数必须跟输入值为何无关)。原因在于,虽然这算法有错误的几率,但是只要我们多进行几次算法,那多数的答案都是错误的几率会呈现指数衰减 [1]页面存档备份,存于互联网档案馆). 因此证明我们可以很简单的架构一个更准确的算法,仅仅单纯多重复几次这个算法然后对每次的答案作多数决。

BPP是大小最大的几个实际的问题类别之一,代表大多数的BPP问题都有有效率的概率算法,因此以上倏地方法可以用现在的机器快速取得解答。因为这个原因,我们对哪一些问题或问题种类在BPP里面有着实用方面的兴趣。

定义

一个语言LBPP里面,当且仅当这语言存在一个概率图灵机 M,另

  • M对任何输入均在多项式时间后停止
  • 对任何字串xL之内, 对M输入x之后,M 输出 1 的几率大于或者等于 2/3
  • 对任何字串 x 不在 L之内, 对M输入x之后,M 输出 1 的几率小于或者等于 1/3

另外,BPP可以仅以决定性图灵机定义。一个语言L是在BPP里面当且仅当存在一个多项式p和一个决定性图灵机M,满足

  • M对任何输入均操作多项式时间之内
  • 对任何字串xL之内, 对长度为 p(|x|)的任意字串y ,满足 M(x,y) = 1 这条件的几率超过或等于2/3
  • 对任何字串 x 不在 L之内, 对长度为 p(|x|)的任意字串 y ,满足 M(x,y) = 1 这条件的几率小于或等于1/3

与其他复杂度类别的关系

已知 BPP 在取补集之下有封闭性; 换句话说, BPP=Co-BPPBPP是否是NP子集仍旧是一个公开的问题。 另外NP是否是BPP的子集也是个公开的问题; 如果是的话,则NP=RP并且PH   BPP([2]) (大多数人认为不会,因为这代表对一些很难的NP-完全 问题有着实际的解法)。现在已知RPBPP的子集,并且BPPPP的子集。 尚不清楚这两个是否为严格子集。 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 KayalNitin Saxena为了这个问题找到了一决定性,多项式时间的算法,因而证实这个问题是在P里面。

一个很重要的范例问题已知在BPP内 (事实上在co-RP内),但不知道是否在P之内。这问题是等同多项式检定, 这问题在于决定一个多项式是否完全等同于一个零多项式。 换句话说,是否存在任何变数数值的组合令这个多项式的结果不为零? 这题目应均匀且随意的从一个至少 d个值的有限集合取变数的值来达到有限几率的错误(d代表多项式的总次数)。[2]

BPP对应于自己 , 代表一个能在常数时间内解决BPP问题的BPP机器 (一个BPP 启示图灵机) ,他的运算能力并不因此比没有这能力的机器更强(或说,两个不同机器定义出来的问题种类维持不变)。

BPP这个语言集合是以一个普通的图灵机加上一个乱数的来源来定义。 相对应的量子计算机语言集合则是BQP

任何在BPP里面的语言可以被多项式大小的布林线路来决定 (参见P/poly).[3]

参考资料

  1. ^ Adleman, L. M. Two theorems on random polynomial time. Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing: 75–83. 1978. 
  2. ^ 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页面存档备份,存于互联网档案馆
  3. ^ Leonard Adleman, Two theorems on random polynomial time, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing, 1978, pp. 75–83.

外部链接