Pseudorandom sources for BPP (Q2641105)

The possibility of replacing independent random bits sequence by pseudorandom bits is investigated. The author considers decision problems computable with bounded error in probabilistic polynomial time (BPP). The following statements are proved: 1) For every BPP-machine almost every sequence in DSPACE(2-linear) is a source for it; 2) Almost every sequence in DSPACE(2-polynomial) is a source for every BPP-machine; 3) Every pspace-random sequence is a source for every BPP-machine. The results are obtained by means of measure theory.