BPP 复杂度类

BPP（Bounded-error Probabilistic Polynomial time，有界错误概率多项式时间）是计算复杂度理论中的一个类，指那些能被概率图灵机在多项式时间内以有界错误概率正确判定的问题。

概述

概率图灵机在运行中可随机掷币选择分支。若对某语言，存在一台多项式时间概率图灵机，使得当输入属于该语言时以至少三分之二概率接受、不属于时以至少三分之二概率拒绝，则该语言属于BPP。这里的常数三分之二可换成任何严格大于二分之一的值，不影响类的定义。

核心特点

• 双侧有界错误：无论输入是否属于语言，出错概率都被一个小于二分之一的常数所限。
• 概率放大：通过独立重复运行并取多数投票，可将错误概率指数级压低，代价仅是多项式倍的时间。
• 包含关系：P包含于BPP，且BPP包含于PH（多项式层级），但BPP与NP的关系尚不明确。
• 对补封闭：由于错误双侧对称，BPP在取补运算下封闭。

核心原理

与BPP相关的还有单侧错误的RP和co-RP、零错误的ZPP等类。当代复杂度理论普遍猜想P等于BPP，即随机性并不能实质增强多项式时间的计算能力。这一猜想由伪随机数生成器与硬度对随机性的转化理论（去随机化）所支撑：若存在足够困难的问题，就能构造伪随机生成器把随机算法确定化。

应用场景

大量高效随机算法落在BPP中，例如早期的素性测试（Miller-Rabin）、多项式恒等测试、随机化的图算法与近似计数。研究BPP的去随机化，有助于理解随机性在算法设计中究竟是本质需求还是可被消除的便利。

常见问题

问：BPP允许算法出错，为何仍被认为可靠？答：因为通过多次独立重复并取多数结果，出错概率可被压到远低于硬件故障率的水平，实际上比确定性程序更可信。

问：P等于BPP已被证明了吗？答：尚未证明，但这是学界普遍相信的猜想，去随机化研究为其提供了强有力的证据。