Изменения
Нет описания правки
# Рассмотрим языки $L_1 = \{\langle \Gamma, A, B\rangle|\Gamma$ - КС-грамматика, $A$ и $B$ - нетерминалы, множество слов, которые можно вывести из $A$ и $B$ совпадают$\}$, $L_2 = \{\langle \Gamma_1, \Gamma_2\rangle|\Gamma_1$ и $\Gamma_2$ - КС-грамматики, языки которых совпадают$\}$. Докажите, что $L_1\le L_2$ и $L_2 \le L_1$. Что можно сказать об $NP$-полноте языков $L_1$ и $L_2$ на основании этого?
# Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = NP$. Прокомментируйте определение Серёжи.
# В этой и следующих заданиях вы можете считать известной $NP$-полноту следующих языков: $3SAT = \{\varphi\,|\,$ существует набор $x$, где $\varphi(x)=1$, причем $\varphi$ находится в 3КНФ $\}$, $IND = \{\langle G, k\rangle\,|\,$ в $G$ существует независимое множество размера $k\}$, $HAM = \{G\,|\,$ в ориентированном графе $G$ существует гамильтонов цикл $\}$, а также всех, $NP$-полнота которых доказана в предыдущих заданиях. Докажите, что задача о клике $NP$-полна.
# Докажите, что задача о вершинном покрытии $NP$-полна.
# Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
# Задача о покрытии подмножествами $NP$-полна. Докажите $NP$-полноту следующего языка. Даны $n$ множеств $S_i\subset\{1, 2, \ldots, m\}$ и число $k$. Язык наборов $SETCOVER = \{ \langle [S_1, S_2, \ldots, S_n], k\rangle$ можно выбрать не более $k$ множеств, чтобы каждый элемент от $1$ до $m$ лежал хотя бы в одном выбранном множестве $\}$.
# Задача реберного покрытия обратных связей $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ - ориентированный граф, который содержит подмножество из $k$ ребер, такое, что любой цикл $G$ содержит хотя бы одно из выбранных ребер $\}$.
# Задача поиска доминирующего множества $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $DOM = \{\langle G, k \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ либо выбрана, либо имеет выбранного соседа $\}$.
# Задача пожарных депо. Докажите $NP$-полноту следующего языка. Множество троек $\{\langle G, k, d \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ имеет выбранную вершину на расстоянии не больше $d\}$.
# Задача о половинной клике. Докажите $NP$-полноту следующего языка. Множество графов $HALFCLIQUE=\{G | G$ имеет клику, содержащую ровно половину вершин $G\}$.
# Задача о раскраске $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $COL=\{\langle G, k\rangle | G$ имеет правильную раскраску в $k$ цветов $\}$.
# Задача о раскраске в три цвета $NP$-полна. Докажите $NP$-полноту следующего языка. Множество графов $3COL=\{ G | G$ имеет правильную раскраску в три цвета $\}$. Что можно сказать про раскраску в два цвета?
# Задача о рюкзаке $NP$-полна. Докажите $NP$-полноту следующего языка. Даны предметы с весом $w_i$ и стоимостью $v_i$. Язык наборов $KNAPSACK=\{ \langle s, [(v_1, w_1), (v_2, w_2), \ldots (v_n, w_n)], k\rangle | $ можно выбрать предметы с суммарным весом не более $s$ и суммарной стоимостью не менее $k \}$.
# Задача целочисленного линейного программирования $NP$-трудна. Докажите $NP$-трудность следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
# Неориентированный гамильтонов цикл. Докажите, что язык $UHAM = \{G | G$ - неориентированный граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
# Ориентированный гамильтонов путь. Докажите, что язык $HAMP = \{G | G$ - ориентированный граф, содержащий гамильтонов путь$\}$ является $NP$-полным.
# Неориентированный гамильтонов путь. Докажите, что язык $UHAMP = \{G | G$ - неориентированный граф, содержащий гамильтонов путь$\}$ является $NP$-полным.
# Выполните явное взаимное сведение языка $HAM = \{G | G$ - ориентированный граф, содержащий гамильтонов цикл$\}$ и языков из предыдущих трех заданий, не обращаясь к общим теоремам типа теоремы Кука.
# Неориентированный планарный гамильтонов цикл. Докажите, что язык $PUHAM = \{G | G$ - неориентированный планарный граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
# Неориентированный гамильтонов цикл в кубическом графе. Докажите, что язык $CUHAM = \{G | G$ - неориентированный кубический граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
# Неориентированный гамильтонов цикл в почти кубическом планарном графе. Докажите, что язык $CPUHAM = \{G | G$ - неориентированный планарный граф, степени вершин которого не превышают 3, содержащий гамильтонов цикл$\}$ является $NP$-полным.
# Задача коммивояжера. Докажите, что язык $WHAM = \{\langle G, w\rangle | G $ - взвешенный ориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
# Задача коммивояжера в неориентированном графе. Докажите, что язык $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$ и его априорное распределение должно быть как у честной монеты.
