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