Просмотр исходного текста страницы Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/las-vegas-k-ammplification

Пусть <tt>A</tt> — вероятностный алгоритм, возращающий или правильный ответ <tt>f(x)</tt>, или «?».
* P(A(x)=f(x)) >= p

Алгоритм <tt>B</tt> —  вызывает <tt>A</tt>, пока не  добьется определенного ответа, но не больше <tt>k</tt> раз.

Оцените <tt>k(q)</tt> — количество повторений для заданного уровня вероятности правильного ответа <tt>q</tt> в алгоритме <tt>B</tt>.


<!--Вообще-то, решения уже есть-->

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]