Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-006 | 1st January 1995 00:00

Pseudorandom Generators, Measure Theory, and Natural Proofs


Authors: Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai
Publication: 1st January 1995 00:00
Downloads: 3230


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.

ISSN 1433-8092 | Imprint