Изменения

Функция <tex> g: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''псевдослучайным генератором'', если <tex> \forall A </tex>, удовл. удовлетворяющего классу [[Сложностный класс BPP|BPP]] , разность вероятностей <tex> |P(A(g(x)) = 1) - P(A(y) = 1)| </tex> -- пренебрежимо мала. Здесь по всем <tex> x \in \{0,1\}^n, y \in \{0,1\}^m </tex>пренебрежимо мала.