Assumptions
- 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.
- We need to store the following state:
This should give us exact acceptance probability in $poly(n)$ time.
Observation
People care about prgs for log space machines.
Question:
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?
Thanks!