Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


  • I believe RL can be derandomized in polynomial time:
    • We need to store the following state:
      • The position of the head on the input.
      • The state of the TM
    • Both can be stored with O(log n) bits.
    • We use dynamic programming, building a table of poly(n) size encapsulating the state of the TM. Then, we march along the random bits, calculating the probability of each TM state after reading a given bit.

This should give us exact acceptance probability in $poly(n)$ time.


People care about prgs for log space machines.


Why? What can we do with a prg for RL that we can't do with an exact acceptance probability algo for RL ?

What is implied by a O(log n) seed length PRG for RL?


share|cite|improve this question

You show that RL$\subseteq$P. Better derandomization could show that RL=L.

share|cite|improve this answer
Is this an implication of log n seed length PRGS? It seems possible to me that such log n seed length PRGS are computable in P but not in L. – user13175 Jan 16 '13 at 18:12
@user13175: If we had log(n) seed length PRGS in L, then RL=L because we just try all the different seeds and take the majority answer. But I'm not sure about the converse (nonexistence of $\log n$ seeds in L $\implies$ RL $\neq$ L). – usul Jan 16 '13 at 22:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.