Yao's test

Boolean circuits

Let P be a polynomial, and S = { S k } k be a collection of sets S k of P ( k ) -bit long sequences, and for each k , let μ k be a probability distribution on S k , and P C be a polynomial. A predicting collection C = { C k } is a collection of boolean circuits of size less than P C ( k ) . Let p k , S C be the probability that on input s , a string randomly selected in S k with probability μ ( s ) , C k ( s ) = 1 , i.e.

Moreover, let p k , U C be the probability that C k ( s ) = 1 on input s a P ( k ) -bit long sequence selected uniformly at random in { 0 , 1 } P ( k ) . We say that S passes Yao's test if for all predicting collection C , for all but finitely many k , for all polynomial Q  :

Probabilistic formulation

As in the case of the next-bit test, the predicting collection used in the above definition can be replaced by a probabilistic Turing machine, working in polynomial time. This also yields a strictly stronger definition of Yao's test (see Adleman's theorem). Indeed, One could decide undecidable properties of the pseudo-random sequence with the non-uniform circuits described above, whereas BPP machines can always be simulated by exponential-time deterministic Turing machines.