ポリロッグランダムビットを用いた$ BPL $は$ L $です

$ BPL
$マシン(すなわち、logspaceと多項式に多くのランダムなビットを使用する確率的アルゴリズム)を考えてみましょう。 $ BPL
subseteq DSPACE(log ^ {1.5}(n))$が知られている(Saks-Zhou)。

私の質問は、ランダム化の多くのビットをポリロッグだけを使用する$ BPL $マシンについてです。
Goldreichの論文の1つでは、このような$ BPL $マシンによって決定された言語は、実際に決定論的なログスペース$ L
$にあると言われています。しかし、私はどこでもこの発言の説明を見つけることができません。

それはなぜlogspaceで完全に逆ランダム化できますか?

ベストアンサー

このNisanとZuckermanのPRG からのものです。この論文では、スペース$ S $と$
mathrm {poly}(S)$ランダムビットのみを使用するアルゴリズムを使用すると、ランダムビットの数を$
O(S)$に減らすことができます。

特に、あなたが説明する設定では、$ S = O( log n)$となるので、ランダムビットの数は$ O( log
n)$に減らすことができます。次に、可能なすべてのコイントーセスを列挙することによってアルゴリズムを完全に逆ランダム化することができます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です