Lower bounds for pseudorandom number generators
Michael Kharitonov, Andrew V. Goldberg, Moti M. Yung · 1989
Computational resources necessary to generate pseudorandom strings are studied. In particular, lower bounds are proved for pseudorandom number generators, whereas previous research concentrated on upper bounds. The idea of separation of machine-based complexity classes on the basis of their ability (or inability) to generate pseudorandom strings is introduced and investigated.>