Pseudorandom sources for BPP

摘要

A source for a probabilistic machine is an infinite binary sequence which can be used in place of random bits without asymptotic loss of performance on any input. Pseudorandom sources-sources which are deterministically computed by time-bounded machines-are investigated. New, measure-theoretic notions of pseudorandomness (“Δ-randomness”) similar to Martin-Löf randomness are defined. The following results are proven: For every BPP-machine M, almost every sequence in DSPACE (2linear) is a source for M. Every pspace-random sequence is a source for every BPP-machine. Almost every sequence in DSPACE (2polynomial) is a source for every BPP-machine.