大家好，欢迎来到IT知识分享网。
在计算复杂度理论里面，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里面有着实用方面的兴趣。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/146622.html
