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.

| cite | improve this answer | |
  • $\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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.