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]