# Computation space of Nisan's generator for space bounded machines

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.

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

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