205
правок
Изменения
м
Нет описания правки
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство<br/><tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>.<br/> Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
== Литература ==
* S.Arora, B.Barak. Randomized computation. Cambridge University, January 2007. [http://www.cs.princeton.edu/theory/complexity/bppchap.pdf]
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
