Изменения

* Функция <tex> \epsilon(n) </tex> называется ''пренебрежимо малой'', если <tex> \forall c > 0 ~</tex> и достаточно больших <tex> n:~\epsilon(n) = o(n^{-c}) </tex>. Пример: <tex> 1/2^n </tex>.* Функция <tex> f </tex> называется ''односторонней'', если для любого полиномиального вероятностного алгоритма <tex> A </tex> существует пренебрежимо малая функция <tex> \forall g epsilon (n)</tex>такая, удовлетворяющей классу [[Сложностный класс BPP|BPP]], что для любого <tex> n </tex> вероятность <tex> PP_{A}(gA(f(x)) = x) < \epsilon (n) </tex> -- пренебрежимо малапо всем <tex> x \in \{0,1\}^n </tex>.