Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR95-006 | 1st January 1995 00:00

#### Pseudorandom Generators, Measure Theory, and Natural Proofs

TR95-006
Authors: Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai
Publication: 1st January 1995 00:00
Keywords:

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.

ISSN 1433-8092 | Imprint