強化学習（複雑性）

ランダム化対数空間( 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を含みます。これは、RL の定義がより一般的であるためです。

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

RL はLに等しい、つまり多項式時間 logspace 計算は完全に非ランダム化できると考えられています。これに関する主要な証拠は、2005 年に Reingold らによって提示されました。 ^{[ 4 ]}この証明は、複雑性クラスの無条件非ランダム化の分野における取り組みの聖杯です。大きな前進は、Omer Reingold によるSLがLに等しいという証明でした。