BPP复杂度

科技工作者之家 2020-11-17

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

要是一个问题在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{\displaystyle \subseteq }BPP([2]) (大多数人认为不会,因为这代表对一些很难的NP-完全问题有着实际的解法)。现在已知RP是BPP的子集,并且BPP是PP的子集。 尚不清楚这两个是否为严格子集。BPP包含在PH里面。因此之故,P=NP代表BPP=P,因为PH在这时会变成P。 存在特定够强的伪乱数产生器是这领域里面大多数专家的猜想。这个猜想代表随机性并不给予多项式计算更多的能力:换句话说,P=RP=BPP。注意一般的产生器并不足以表示出结果;使用典型的乱数产生器实做的任何概率算法,与乱数的种子无关,对某一些特定的输入会一直给出错误的答案(即使这一些输入可能很稀少)。我们也可得到P=BPP,若指数时间等级等同于(Babai et al.),或者若E有指数的电路复杂性(Impagliazzo and Wigderson)。 又BPP包含在里面,若EXPTIME并不等同于

一个Monte Carlo算法是一个"差不多正确"的随机算法。 与跟它很像的拉斯维加斯算法比较,后者则是一个永远正确的随机算法,不过随机性在于有可能会回传推算失败。多项式时间之内的拉斯维加斯算法可以用来定义ZPP这个复杂度类。1

BPP包含在P/poly里面, 根据Adleman的理论,BPP是包含于P (复杂度)里面的。; 的确,根据这个事实证明的结果,每一个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里面的语言可以被多项式大小的布林线路来决定。

本词条内容贡献者为:

黎明 - 副教授 - 西南大学

科技工作者之家

科技工作者之家APP是专注科技人才,知识分享与人才交流的服务平台。