Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Необратимое семейство перестановок — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]])
Строка 3: Строка 3:
 
Необратимость означает, что для любого вероятностного полиномиального алгоритма <m>A</m> для всех достаточно больших <m>n</m> вероятность события <m>A(f_n(x))=x</m> меньше (случайно взятый <m>x</m> длины <m>n</m> и случайное бросание алгоритма).
 
Необратимость означает, что для любого вероятностного полиномиального алгоритма <m>A</m> для всех достаточно больших <m>n</m> вероятность события <m>A(f_n(x))=x</m> меньше (случайно взятый <m>x</m> длины <m>n</m> и случайное бросание алгоритма).
  
[[Категория:Решенные задачи]]
+
[[Категория:Нерешенные задачи]]

Версия 20:59, 20 сентября 2018

Доказать, что существует необратимое семейство перестановок (под перестановками подразумеваются биекции).

Необратимость означает, что для любого вероятностного полиномиального алгоритма для всех достаточно больших вероятность события меньше (случайно взятый длины и случайное бросание алгоритма).