Abstract:
This paper proves that if strong pseudorandom number generators or one-way functions exist, then the class of languages that have polynomial-sized circuits is not small within exponential time, in terms of the resource-bounded measure theory of Lutz. More precisely, if for some \epsilon > 0 there exist nonuniformly 2^{n^{\epsilon}}-hard PSRGs, as is widely believed, then P/poly does not have measure zero in EXP. Our results establish connections between the measure theory and the ``natural proofs'' of Razborov and Rudich. Our work is also motivated by Lutz's hypothesis that NP does not have measure zero in EXP; obtaining our results with NP in place of P/poly would show much more far-reaching consequences from the existence of PSRGs than are currently known.