Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Необратимое семейство перестановок
Материал из DISCOPAL
< Вероятностные вычисления. Классы RP, coRP, ZPP, BPP | Задачи
Версия от 20:58, 20 декабря 2012; Felagund (обсуждение) (Created page with "Category:Предложенные студентами задачи Доказать, что существует необратимое семейство перест...")
Доказать, что существует необратимое семейство перестановок (под перестановками подразумеваются биекции). Необратимость означает, что для любого вероятностного полиномиального алгоритма для всех достаточно больших вероятность события меньше (случайно взятый длины и случайное бросание алгоритма).
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.