BPP 的定义
一个判定问题属于 BPP 类，如果存在一个概率图灵机（PTM）A，使得：
- 对于输入 x，如果 x 在问题中，那么 A 在多项式时间内接受 x 的概率至少为 2/3。
- 对于输入 x，如果 x 不在问题中，那么 A 在多项式时间内拒绝 x 的概率至少为 2/3。
这意味着，对于每个输入，PTM 都会在多项式时间内给出正确的答案，但存在一个小的错误概率。这个错误概率是有界的，也就是说，错误出现的概率不会超过一个固定的常数，例如 1/3。 我们可以通过多次运行算法，并取多数结果来降低错误概率。
BPP 的重要性
BPP 类在理论计算机科学中占有重要地位。以下是 BPP 的几个关键方面：
- 实际应用：许多实际问题都有有效的 BPP 算法，例如素性测试。尽管存在确定性的算法，但 BPP 算法在实践中可能更有效。
- 概率算法的优势： BPP 表明概率算法有时可以比确定性算法更有效，或者能够解决确定性算法难以解决的问题。
- 理论挑战：一个核心的理论问题是，BPP 是否等于 P（确定性多项式时间）。 如果 BPP = P，这意味着任何可以用概率算法有效解决的问题也可以用确定性算法有效解决。这是一个未解决的问题，也是计算复杂性领域的一个活跃研究方向。
BPP 与其他复杂度类的关系
BPP 与其他复杂度类之间存在着紧密的联系，理解这些关系有助于更好地理解 BPP 的性质。 以下是几个关键的比较：
- P：显然，P ⊆ BPP，因为任何可以在多项式时间内使用确定性算法解决的问题，都可以通过概率算法解决，只需忽略随机性即可。
- RP 和 co-RP： BPP 包含了 RP（随机多项式时间）和 co-RP，RP 和 co-RP 分别代表单边错误概率的多项式时间算法。RP 允许在输入不属于问题时有较小的错误概率，而 co-RP 允许在输入属于问题时有较小的错误概率。
- NP： 目前，我们不知道 BPP 和 NP 之间的确切关系。BPP 是否包含 NP，或者 NP 是否包含 BPP，都是未解之谜。
BPP 的性质
BPP 具有一些重要的性质，这些性质对研究它的计算能力至关重要。
- 错误概率的降低： 可以通过多次独立运行 BPP 算法来降低错误概率，然后取多数结果。例如，如果运行算法 100 次，错误概率会变得非常小，接近于 2^(-100)。
- 去随机化： 虽然目前无法确定性地证明 BPP = P，但研究人员已经开发了一些“去随机化”技术，用于将 BPP 算法转换为确定性算法，在特定条件下，可以减少对随机性的依赖。
结论
BPP 是一个重要的复杂度类，它描述了可以用概率算法在多项式时间内解决的问题。虽然 BPP 的确切性质和与其他复杂度类的关系仍然是研究的热点，但它在计算机科学领域，特别是在算法设计和复杂性理论中，具有重要的理论和实践意义。 BPP 算法的有效性展示了概率算法在解决某些计算问题上的强大能力，并促使我们更深入地理解计算的本质和极限。