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]