94-17 Normal Numbers and Sources for BPP

DIMACS TR: 94-17

Normal Numbers and Sources for BPP

Author: Martin Strauss

ABSTRACT
Lutz proposed a notion of source, a nonrandom sequence that can substitute in a certain way for the random bits used by bounded-error probabilistic machines. He showed that almost every sequence in DSPACE(2^polynomial) is a source. We improve this abundance result to PSPACE, by first showing that the sources are exactly the classical normal numbers of Borel. We go on to show there are sources in AC0. Unfortunately, this suggests that alternate notions of source should be explored.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-17.ps

DIMACS Home Page