<p>Well, here are a couple of observations. There's <a href="https://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Nisan_PRG.pdf" rel="nofollow noreferrer">a famous PRG by Nisan</a> that fools <span class="math-container">$\mathsf{BPL}$</span>-type algorithms with seed length <span class="math-container">$O(\log^2 n)$</span>. Given two-way access to the seed, Nisan's PRG can be computed in space <span class="math-container">$O(\log n)$</span>. Therefore, every language in <span class="math-container">$\mathsf{BPL}$</span> can be decided by a <span class="math-container">$\mathsf{BP}^*\mathsf{L}$</span>-type algorithm that only uses <span class="math-container">$O(\log^2 n)$</span> random bits.</p>

<p>In fact, you can get the best of both worlds. By using the same technique that Nisan <a href="https://dl.acm.org/doi/10.1145/129712.129772" rel="nofollow noreferrer">used</a> to show <span class="math-container">$\mathsf{RL} \subseteq \mathsf{SC}$</span>, one can show that every language in <span class="math-container">$\mathsf{BPL}$</span> can be decided by a <span class="math-container">$\mathsf{ZP}^*\mathsf{L}$</span>-type algorithm that only uses <span class="math-container">$O(\log^2 n)$</span> random bits.</p>

<p>So in terms of the state of the art, two-way randomness is more powerful both qualitatively (two-sided error vs. zero-sided error) and quantitatively (polynomially many random bits vs. polylogarithmically many random bits). However, it seems likely that <span class="math-container">$\mathsf{L} = \mathsf{BP}^*\mathsf{L}$</span> and hence the two models are actually equivalent.</p>

CC BY-SA 4.0
2020-01-30T18:52:22.550Z
2020-01-30T18:52:22.550Z
William Hoza
<p>Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the random tape.  </p>

<p>Let $\mathsf{ZP^*L}$/$\mathsf{R^*L}$/$\mathsf{BP^*L}$ denote the corresponding classes by replacing one-way to two-way access.  We have the normal inclusions $\mathsf{ZPL} \subseteq\mathsf{RL}\subseteq\mathsf{BPL}$ and $\mathsf{ZP^*L} \subseteq\mathsf{R^*L}\subseteq\mathsf{BP^*L}$.</p>

<p>In the following paper, </p>

<blockquote>
  <p><a href="http://www.google.com.tw/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;ved=0CCoQFjAA&amp;url=http://www.cs.huji.ac.il/~noam/otway.ps&amp;ei=3GZRUIa2CeLkygHMzYHABg&amp;usg=AFQjCNFx98mhnv7p-a_GTfkeNHIYhsA-3w">On Read-Once vs. Multiple Access to Randomness in Logspace</a>, Noam Nisan, 1995</p>
</blockquote>

<p>he prove that $\mathsf{BPL} \subseteq \mathsf{ZP^*L}$, which is rather surprising because it seems that two-way access may be stronger than the one-way access.</p>

<blockquote>
  <p><strong>Question.</strong>  Do we have any further results which demonstrate the power of two-way access randomized logspace?  </p>
</blockquote>

CC BY-SA 3.0
2012-09-13T16:18:16.400Z
The answer might be in [Computationally Limited Randomness](http://itcs.tsinghua.edu.cn/~papakons/pdfs/ICS11.pdf)
Kaveh
CC BY-SA 3.0
2012-09-15T15:27:02.350Z
Although they are not directly related, you might check the following two papers: On some variations of two-way probabilistic finite automata models by Ravikumar (http://dx.doi.org/10.1016/j.tcs.2007.01.017) and Multiple Usage of Random Bits in Finite Automata by Freivalds (http://dx.doi.org/10.1007/978-3-642-29952-0_50).
Abuzer Yakaryilmaz
<cc.complexity-theory><complexity-classes><turing-machines><randomness>
The power of randomized logspace with two-way access to the random tape
Hsien-Chih Chang 張顯之
# The power of randomized logspace with two-way access to the random tape

(Asked by: username_0 on 2012-09-13)

Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the random tape.

Let $\mathsf{ZP^\*L}$/$\mathsf{R^\*L}$/$\mathsf{BP^\*L}$ denote the corresponding classes by replacing one-way to two-way access. We have the normal inclusions $\mathsf{ZPL} \subseteq\mathsf{RL}\subseteq\mathsf{BPL}$ and $\mathsf{ZP^\*L} \subseteq\mathsf{R^\*L}\subseteq\mathsf{BP^\*L}$.

In the following paper,

> [On Read-Once vs. Multiple Access to Randomness in Logspace](http://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCoQFjAA&url=http://www.cs.huji.ac.il/~noam/otway.ps&ei=3GZRUIa2CeLkygHMzYHABg&usg=AFQjCNFx98mhnv7p-a_GTfkeNHIYhsA-3w), Noam Nisan, 1995

he prove that $\mathsf{BPL} \subseteq \mathsf{ZP^\*L}$, which is rather surprising because it seems that two-way access may be stronger than the one-way access.

> **Question.** Do we have any further results which demonstrate the power of two-way access randomized logspace?

**Tags:** cc.complexity-theory, complexity-classes, turing-machines, randomness

> **Comments:**
> **username_1**: The answer might be in [Computationally Limited Randomness](http://itcs.tsinghua.edu.cn/~papakons/pdfs/ICS11.pdf)  
> **username_2**: Although they are not directly related, you might check the following two papers: On some variations of two-way probabilistic finite automata models by Ravikumar (http://dx.doi.org/10.1016/j.tcs.2007.01.017) and Multiple Usage of Random Bits in Finite Automata by Freivalds (http://dx.doi.org/10.1007/978-3-642-29952-0_50).  

---

## 1 answers

### Answer by username_3 on 2020-01-30. Score: 3

Well, here are a couple of observations. There's [a famous PRG by Nisan](https://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Nisan_PRG.pdf) that fools $\mathsf{BPL}$-type algorithms with seed length $O(\log^2 n)$. Given two-way access to the seed, Nisan's PRG can be computed in space $O(\log n)$. Therefore, every language in $\mathsf{BPL}$ can be decided by a $\mathsf{BP}^\*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)$ random bits.

In fact, you can get the best of both worlds. By using the same technique that Nisan [used](https://dl.acm.org/doi/10.1145/129712.129772) to show $\mathsf{RL} \subseteq \mathsf{SC}$, one can show that every language in $\mathsf{BPL}$ can be decided by a $\mathsf{ZP}^\*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)$ random bits.

So in terms of the state of the art, two-way randomness is more powerful both qualitatively (two-sided error vs. zero-sided error) and quantitatively (polynomially many random bits vs. polylogarithmically many random bits). However, it seems likely that $\mathsf{L} = \mathsf{BP}^\*\mathsf{L}$ and hence the two models are actually equivalent.


---

