In cryptography and the theory of computation, Yao's test is a test defined by Andrew ChiChih Yao in 1982 ^{[1]}, against pseudorandom sequences. A sequence of words passes Yao's test if an attacker with reasonable computational power cannot distinguish it from a sequence generated uniformly at random.
Contents 
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 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 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 :
As in the case of the nextbit 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 pseudorandom sequence with the nonuniform circuits described above, whereas BPP machines can always be simulated by exponentialtime deterministic Turing machines.
