Pseudorandom generator

Summary

A pseudorandom generator stretches a short uniformly random seed into a long string that no efficient test can tell apart from a uniformly random string. In complexity theory the tests are Boolean circuits of bounded size, or algorithms of bounded running time. Derandomization is the use of such generators to replace the random bits of an algorithm, which turns randomised algorithms into deterministic ones. Good enough generators, with seed length logarithmic in the output length, would give $\mathrm{BPP} = \mathrm{P}$.