<p>Yes, I believe that is correct. See, for example, these <a href="http://www.cs.umd.edu/~jkatz/complexity/f11/lecture27.pdf" rel="nofollow">lecture notes</a>.</p>

CC BY-SA 3.0
2012-03-23T01:17:30.937Z
thanks for the link...yes, it looks like $O(S\log (R/S))$ computation space for the generator will be sufficient.
Debasis
CC BY-SA 3.0
2012-03-22T10:37:54.770Z
2012-03-22T10:37:54.770Z
user6584
<p>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?</p>

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

CC BY-SA 3.0
2012-03-20T08:59:11.427Z
Maybe @Noam Nisan will stop by to answer :)
Suresh Venkat
<cc.complexity-theory>
Computation space of Nisan's generator for space bounded machines
Debasis
# Computation space of Nisan's generator for space bounded machines

(Asked by: username_0 on 2012-03-20)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Maybe @Noam Nisan will stop by to answer :)  

---

## 1 answers

### Answer by username_2 on 2012-03-22. Score: 1 | Accepted answer

Yes, I believe that is correct. See, for example, these [lecture notes](http://www.cs.umd.edu/~jkatz/complexity/f11/lecture27.pdf).

> **Comments:**
> **username_0**: thanks for the link...yes, it looks like $O(S\log (R/S))$ computation space for the generator will be sufficient.  

---

