ECCC-Report TR95-006https://eccc.weizmann.ac.il/report/1995/006Comments and Revisions published for TR95-006en-usSun, 01 Jan 1995 00:00:00 +0200
Paper TR95-006
| Pseudorandom Generators, Measure Theory, and Natural Proofs |
Kenneth W. Regan,
D. Sivakumar,
Jin-Yi Cai
https://eccc.weizmann.ac.il/report/1995/006
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.
Sun, 01 Jan 1995 00:00:00 +0200https://eccc.weizmann.ac.il/report/1995/006