Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Необратимое семейство перестановок — различия между версиями
Материал из DISCOPAL
(Created page with "Category:Предложенные студентами задачи Доказать, что существует необратимое семейство перест...") |
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> и случайное бросание алгоритма). | ||
| + | |||
| + | [[Category:Решенные задачи]] | ||
Версия 10:02, 20 мая 2015
Доказать, что существует необратимое семейство перестановок (под перестановками подразумеваются биекции). Необратимость означает, что для любого вероятностного полиномиального алгоритма для всех достаточно больших вероятность события меньше (случайно взятый длины и случайное бросание алгоритма).