Pseudorandom sources for BPP
Jack H. Lutz · 1988
A computational problem is considered feasible if it can be solved in polynomial time with arbitrarily low probability of error by a probabilistic algorithm. In principle, such an algorithm requires a generous (infinite) source of independent random bits, but it is generally assumed that it will perform equally well when supplied with a deterministically computed sequence of pseudorandom bits. The question of which pseudorandom sequences are sufficiently random to justify this assumption is addressed. Novel measure-theoretic notions of pseudorandomness ( Delta -randomness) similar to Martin-Lof randomness are defined. A uniform, resource-bounded generalization of the classical first Borel-Cantelli lemma is proved and used in turn to prove the following: (1) for every BPP-machine M, almost every sequence in ESPACE is a source for M; (2) every pspace-random sequence is a source for BPP; and (3) almost every sequence in E/sub 2/SPACE is a source for BPP.>