9
$\begingroup$

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, 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?

$\endgroup$
3
$\begingroup$

Well, here are a couple of observations. There's a famous PRG by Nisan 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 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.