92
правки
Изменения
м
→Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
{{Определение
|definition=Язык <tex>L</tex> принадлежит сложностному [[RP|классу <tex>''RP</tex>'']], если существует полиномиальный алгоритм <tex>A</tex> такой что
1. для <tex>x \in L</tex> для всех <tex>r \in \{0, 1\}^{poly(n)}</tex> <tex>A(x, r) = 1</tex>
2. для <tex>x \notin L</tex> не более чем для 1/2000 всех <tex>r \in \{0, 1\}^{poly(n)}</tex> может выполняться <tex>A(x, r) = 1</tex>
