BPL (複雑さ)

計算複雑性理論において、BPL（誤差限定確率対数空間）^[1]は、 BPLP（誤差限定確率対数空間多項式時間）^[2]とも呼ばれ、両側誤差を持つ確率チューリングマシンで対数空間と多項式時間で解ける問題の計算複雑性クラスである。これは、類似しているが対数空間の制限がないBPPとの類推で名付けられている。

BPLの定義における確率的チューリングマシンは、1/3 未満の確率でのみ誤って受け入れたり拒否したりすることがあります。これは両側誤差と呼ばれます。定数 1/3 は任意です。0 ≤ x < 1/2 の任意のxで十分です。この誤差は、アルゴリズムを繰り返し実行することで、多項式時間または対数空間を超えることなく、任意の多項式p ( x ) に対して 2 ^{− p ( x )}倍小さくすることができます。

両側誤差は片側誤差よりも一般的であるため、RLとその補数 co-RL はBPLに含まれます。BPLはPLにも含まれますが、これは誤差境界が 1/2 未満の定数ではなく 1/2 である点を除いて同様です。クラスPPと同様に、クラスPL は、誤差確率を小さな定数に減らすために多数のラウンドを必要とする可能性があるため、あまり実用的ではありません。

Nisan (1994) は、 BPL がSCに含まれるという弱いデランダム化の結果を示しました。^[3] SC は、決定論的チューリングマシン上で多項式時間と多項式空間で解ける問題のクラスです。言い換えれば、この結果は、多項式空間が与えられれば、決定論的マシンは対数空間確率アルゴリズムをシミュレートできることを示しています。

BPLはNCとL/polyに含まれています。SaksとZhouは、 BPLがDSPACE（log ^3/2 n）に含まれていることを示しました^{[4] 。そして2021年にHozaはこれを改良し、} BPLがDSPACE に含まれていること を示しました^[5]。${\displaystyle (\log ^{3/2}(n)/{\sqrt {\log \log n}})}$