RL（複雑さ）

ランダム化対数空間（RL）^[1]は、 RLP（ランダム化対数空間多項式時間）^[2 ]とも呼ばれ、片側誤差を持つ確率的チューリングマシンを使用して対数空間と多項式時間で解ける計算複雑性理論の問題の複雑性クラスです。これは、類似しているが対数空間の制限がないRPとの類似性から名付けられました。

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

RLという名前は、無制限の時間で対数空間の確率マシンによって解決可能な問題のクラスを指すために予約されていることがあります。ただし、このクラスは確率カウンタを使用してNLと等しいことが示されるため、通常は代わりにNLと呼ばれます。これは、RLがNLに含まれることも示しています。RLはBPLに含まれており、BPL は似ていますが、両側エラー (誤った受け入れ) を許容します。RL には、定義がより一般的なため、対数空間の 決定論的チューリングマシンによって解決可能な問題であるLが含まれます。

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

RL はLに等しい、つまり多項式時間対数空間計算は完全にランダム化解除できると考えられており、その主要な証拠は2005年にReingoldらによって提示されました。 ^{[4]この証明は、複雑性クラスの無条件ランダム化解除の分野における努力の究極の目標です。大きな前進は、Omer Reingoldによる}SL はLに等しいという証明でした。