Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Необратимое семейство перестановок — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]]) |
StasFomin (обсуждение | вклад) |
||
Строка 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> и случайное бросание алгоритма). | ||
− | [[ | + | [[Категория:Нерешенные задачи]] |
Версия 11:45, 18 декабря 2017
Доказать, что существует необратимое семейство перестановок (под перестановками подразумеваются биекции).
Необратимость означает, что для любого вероятностного полиномиального алгоритма для всех достаточно больших вероятность события меньше (случайно взятый длины и случайное бросание алгоритма).