1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Задача коммивояжера в неориентированном графе. Докажите, что язык $WUHAM = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
# Задача коммивояжера в неориентированном графе без вершин степени 2. Докажите, что язык $WUHAN = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором нет вершин степени 2 и существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
# Докажите, что $ZPP = RP \cap coRP$.
# Докажите, что $BPP \subset PS$.
# Докажите, что $RP \subset NP$.
# Обозначим как $PP^+$ как класс языков, для которых существует вероятностная программа $M$, работающая за полином, что если $x \in L$, то $P(M(x) = 1) > 1/2$, а если $x \notin L$, то $P(M(x) = 0) \ge 1/2$. Докажите, что $PP^+ = PP$.
# Докажите, что $NP \subset PP$.
# Докажите, что если $NP \subset BPP$, то $NP = RP$.
# В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.
# При симуляции $random(n)$ с помощью бросков честной монеты (или абстракции вероятностной ленты) математическое ожидание времени работы $random(n)$ равно $O(\log n)$, но нет ограничения сверху на число бросков. Кажется, что это может испортить определение классов $RP$ или $BPP$, потому что в них время работы программы должно быть ограничено сверху. Докажите, что это не так и можно разрешить конструкции $random(n)$ в вероятностных программах из определения $RP$ или $BPP$, даже если на самом деле в модели вычислений есть доступ к источнику случайности только с распределением честной монеты.
# Пусть $n = pq$, предложите полиномиальный алгоритм, который по заданным $n$ и $\varphi(n)$ находит $p$ и $q$.
# Факторизация через взлом RSA. Пусть $n = pq$, $ed = 1 \pmod{\varphi(n)}$, полиномиальный алгоритм по заданным $n$ и $e$ находит $d$. Докажите, что существует полиномиальный алгоритм, который по заданному $n$ находит $p$ и $q$.
# Плохое $e$. Почему в алгоритме RSA нельзя использовать $e=2$?
# Плохое $e$. Петя отправляет сообщение $x$ Алисе, Бобу и Чарли. Они все трое используют RSA с открытым ключом $e=3$ и разными $n_1$, $n_2$ и $n_3$. Помогите злоумышленнику, который перехватил все три зашифрованных сообщения, восстановить $x$. Сможет ли он восстановить $d_i$?
# Переиспользование $n$. Петя отправляет сообщение $x$ Алисе и Бобу. Оба используют RSA с открытыми ключами $e_1$ и $e_2$ ($e_1$ и $e_2$ взаимно просты) и одинаковым $n$. Помогите злоумышленнику, который перехватил оба зашифрованных сообщения, восстановить $x$. Сможет ли он восстановить $d_i$?
# Бросок монеты по телефону. Используя алгоритм слепой цифровой подписи предложите алгоритм, который позволяет Алисе и Бобу подбросить честную монету по телефону. Честная монета у каждого из них есть, в результате общения каждый из них должен иметь одно и то же значение $x$ и его априорное распределение должно быть как у честной монеты.
