Изменения

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

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

Функция <tex> g G </tex> является случайным генератором тогда и только тогда, когда <tex> g G </tex> - непредсказуемая.