In cryptography and the theory of computation, the next-bit test is a test against pseudo-random number generatorsst with reasonable computational power.

Precise statement(s)

be the probability distribution.

We now define the next-bit test in two different ways.

Boolean circuit formulation

A predicting collection is a collection of boolean circuits, i.e. : :

Probabilistic Turing machines

We can also define the next-bit test in terms of probabilistic Turing machines, although this definition is somewhat stronger (see Adleman's theorem be a probabilistic Turing machine, working in polynomial timest bit correctly, i.e. :

Completeness for Yao's test

The next-bit test is a particular case of Yao's test for random sequences, and passing it is therefore a necessary condition for passing Yao's test. However, it has also been shown a sufficient condition by Yao.

We prove it now in the case of the probabilistic Turing machine, since Adleman has already done the work of replacing randomization with non-uniformity in his theorem. The case of Boolean circuits cannot be derived from this case (since it involves deciding potentially undecidable problems), but the proof of Adleman's theorem can be easily adapted to the case of non-uniform Boolean circuit families.

.

remaining bits uniformly at random. We have thus:

a polynomial.

else.

References