BPL_(complexity)
で計算複雑性理論、BPL（有界誤差確率対数空間）、と呼ばれることもあるBPLP（有界誤差確率対数空間多項式時間）、である複雑性クラスで解ける問題の対数空間と多項式時間と確率的チューリングマシンとの両面エラー。これは、BPPと同様に名前が付けられています。これは類似していますが、対数空間の制限はありません。
エラーモデル
BPLの定義における確率的チューリングマシンは、1/3未満の時間でのみ誤って受け入れまたは拒否する可能性がこれは両面エラーと呼ばれます。定数1/3は任意です。任意のXと0≤ X
関連クラス
両側エラーは片側エラーよりも一般的であるため、RLとその補数 co-RLはBPLに含まれています。BPLもPLに含まれています。これは、エラー限界が1/2未満の定数ではなく、1/2であることを除いて同様です。クラスPPと同様に、クラスPLは、エラー確率を小さな定数に減らすために多数のラウンドを必要とする可能性があるため、あまり実用的ではありません。
Nisan（1994）は、BPLがSCに含まれているという弱い非ランダム化の結果を示しました。 SCは、決定論的チューリングマシンの多項式時間と多項式空間で解ける問題のクラスです。言い換えると、この結果は、多対数空間が与えられた場合、決定論的マシンが対数空間の確率的アルゴリズムをシミュレートできることを示しています。
BPLはNCとL / polyに含まれています。SaksとZhouは、BPLがDSPACEに含まれていることを示しました（log 3/2 n）。2021年にHozaはこれを改善して、BPLがDSPACEに含まれていることを示しました。（（ ログ3 / 2（（ ）。 / ログ
ログ
NS）。
{ displaystyle（ log ^ {3/2}（n）/ { sqrt { log log n}}）}
。
参考文献
^ 「複雑性動物園：BPL」。
^ ボロディン、A。; クック、SA ; ダイモンド、PW; ルッツォ、WL; Tompa、M。（1989）、「相補性問題に対する帰納的カウントの2つのアプリケーション」、SIAM Journal on Computing、18（3）：559–578、CiteSeerX 10.1.1.394.1662、doi：10.1137 / 0218038 ^ Nisan、N。（1994）、「RL⊆SC」、計算の複雑さ、4（1）：1–11、doi：10.1007 / BF01205052、この論文の以前のバージョンは、1992年の計算理論シンポジウムに掲載されました。
^ 複雑性理論の講義ノート ^ “