Изменения
→Определения
* Функция <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> \epsilon (n)</tex> такая, что для любого натурального <tex> n </tex> вероятность <tex> P_{A}(A(f(x)) = x) < \epsilon (n)</tex> по всем <tex> x \in \{0,1\}^n </tex>.
== Гипотеза ==
