Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/las-vegas-k-ammplification — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена Решенные задачи]] на Нерешенные задачи)
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
Пусть <tt>A</tt> — вероятностный алгоритм, возращающий или правильный ответ (<tt>f(x)</tt>), или «?».
+
Пусть <tt>A</tt> — вероятностный алгоритм, возращающий или правильный ответ <tt>f(x)</tt>, или «?».
 
* P(A(x)=f(x)) >= p
 
* P(A(x)=f(x)) >= p
  
 
Алгоритм <tt>B</tt> —  вызывает <tt>A</tt>, пока не  добьется определенного ответа, но не больше <tt>k</tt> раз.
 
Алгоритм <tt>B</tt> —  вызывает <tt>A</tt>, пока не  добьется определенного ответа, но не больше <tt>k</tt> раз.
  
Оцените, <tt>k(q)</tt> — количество повторений для заданного уровня вероятности правильного ответа <tt>q</tt> в алгоритме <tt>B</tt>.
+
Оцените <tt>k(q)</tt> — количество повторений для заданного уровня вероятности правильного ответа <tt>q</tt> в алгоритме <tt>B</tt>.
  
  
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
  
[[Категория:Нерешенные задачи
+
[[Категория:Решенные задачи]]

Версия 15:49, 20 мая 2020

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

  • P(A(x)=f(x)) >= p

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

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