BPL (复杂度)

在计算复杂度理论领域内，BPL（有限错误几率对数空间，Bounded-error Probabilistic Logarithmic-space）^[1]或者叫做BPLP（有限错误几率对数空间多项式时间，Bounded-error Probabilistic Logarithmic-space Polynomial-time）^[2]是一个使用几率图灵机可以在多项式时间时间以及对数空间解决的问题，但是有双边错误（two-sided error）。这个类别的名称类似BPP，一个很接近但是没有对数空间限制的类别。

BPL里面的几率图灵机会在回答接收或者拒绝的时候，犯下几率小于1/3的错误；这个被称呼为双边错误。

这里1/3的常数是一个抽象的概念：任何0 ≤ x < 1/2都可以满足这个定义。借由重复整个算法，我们可以限缩误差几率小于2^−p(x)（这里的p(x)为任意多项式），并且不使用多项式时间和对数空间以上的资源。

虽然双边错误比起单边错误（回答特定答案时绝不会出错，只有在另一个答案时会）更加一般化，RL和它的补集co-RL包含在BPL里面。BPL也包含在PL（一个相类似的复杂度类，不过其错误率恰为1/2而非小于1/2）里面；就像PP一样，PL可能需要花费很多次的计算来降低错误的几率，因此比较不实用。

Nisan (1994)使用了一个弱的去随机化结果证明BPL包含在SC里面。^[3]这里的SC是一个复杂度类，包含可以使用决定型图灵机在多项式时间和多项式对数（polylogarithmic）空间解决的问题；换句话说，这个结论证明了给予多项式对数空间，一个决定型机器可以模拟对数空间的几率算法。

参考资料

^ Complexity Zoo: BPL. [2010-10-19]. （原始内容存档于2010-07-27）.
^ Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M., Two applications of inductive counting for complementation problems, SIAM Journal on Computing, 1989, 18 (3): 559–578, doi:10.1137/0218038 .
^ Nisan, N., RL ⊆ SC, Computational Complexity, 1994, 4 (1): 1–11, doi:10.1007/BF01205052, An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing .

[1] Complexity Zoo: BPL. [2010-10-19]. （原始内容存档于2010-07-27）.

[2] Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M., Two applications of inductive counting for complementation problems, SIAM Journal on Computing, 1989, 18 (3): 559–578, doi:10.1137/0218038 .

[3] Nisan, N., RL ⊆ SC, Computational Complexity, 1994, 4 (1): 1–11, doi:10.1007/BF01205052, An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing .

[1]

[2]

[3]