檢視 BPL(複雜度) 的原始碼

佇咧算複雜度理論領域內，'''BPL'''（有限錯誤的機率對數空間，Bounded-error Probabilistic Logarithmic-space）抑是講號做'''BPLP'''（有限錯誤機率對數空間多項式時間，Bounded-error Probabilistic Logarithmic-space Polynomial-time）是一種使用機率圖靈機會當佇多項式時間時間佮對數空間解決的問題，但是有'''雙爿錯誤'''（two-sided error）。 這个類別的名稱類似'''BPP'''，一个誠倚但是無對數空間的限制的類別。

'''BPL'''內底的機率圖靈機會咧回答接收抑是拒絕的時，犯下機率細漢佇三分之一的錯誤；這个予人稱呼做 _ 雙爿錯誤 _。

遮三分之一的常數是一个抽象的概念：任何零 ≤ _ x _ < 二分之一攏會當滿足這个定義。藉著重複規个演算法，咱會使限縮差機率細漢兩 − _ p _ ( _ x _ )（遮的 _ p _ ( _ x _ ) 為任意多項式）， 並且無使用濟項式時間佮對數空間以上的資源。

雖然雙爿錯誤比起單爿錯誤（回答特定答案的時絕對袂脫箠，干焦佇另外一个答案的時陣會）閣較一般化，'''RL'''佮伊的補集'''co-RL'''包括佇'''BPL'''內底。'''BPL'''嘛包括講佇咧'''PL'''（一个相類似的複雜度類，不過其錯誤率恰為而兩分之一而非小於二分之一）內底；就親像'''PP'''仝款，'''PL'''可能是需要開足濟改的計算來降低錯誤的機率，就按呢較無實用。

Nisan ( 一千九百九十四 ) 會當使用一个弱的去隨機化結果證明'''BPL'''包括佇'''SC'''內底。遮的 SC 是一个複雜度類，包含會使用決定型圖靈機佇多項式時間佮多項式對數（polylogarithmic）空間解決的問題；嘛會使講，這个結論證明矣予 _ 多項式對數 _ 空間，決定型機器會當模擬 _ 對數 _ 空間的機率演算法。

==參考資料==

[[分類: 待校正]]