This is probably a very trivial question. Suppose a space($S$) machine uses $R$ random bits. Then Nisan's PRG for space bounded machines can fool it using a seed of length $O(S\log (R/S))$. Theorem 1 in section 4 also mentions that this PRG can be computed in space $O(S\log R)$. This is due to the fact that we need to store $\log R$ many hash functions, each of $O(S)$ space. My questions is, can we say that the PRG can be computed in space $O(S\log (R/S))$ (to produce $R$ bits as above) as well in stead of $O(S\log R)$? That is, can we use just $\log (R/S)$ hash functions?

Reference paper: N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica, vol. 12, no. 4, pp. 449-461, Dec. 1992.

  • 2
    $\begingroup$ Maybe @Noam Nisan will stop by to answer :) $\endgroup$ – Suresh Venkat Mar 20 '12 at 8:59

Yes, I believe that is correct. See, for example, these lecture notes.

  • $\begingroup$ thanks for the link...yes, it looks like $O(S\log (R/S))$ computation space for the generator will be sufficient. $\endgroup$ – Debasis Mar 23 '12 at 1:17

Your Answer

