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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи на :Решенные задачи)
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 9 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Доказать, что существует необратимое семейство перестановок <m>f_n:\{0,1\}^n \rightarrow \{0,1\}^n</m> (под перестановками подразумеваются биекции).
 
Доказать, что существует необратимое семейство перестановок <m>f_n:\{0,1\}^n \rightarrow \{0,1\}^n</m> (под перестановками подразумеваются биекции).
 +
 
Необратимость означает, что для любого вероятностного полиномиального алгоритма <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> и случайное бросание алгоритма).
  
[[Category:Решенные задачи]]
+
[[Категория:Решенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:50, 4 мая 2023

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

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