Редактирование: Список заданий по теории сложности lite 2021

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 12: Строка 12:
 
# $PRIMES\in NP$. Язык $PRIMES$ определяется следующим образом: это множество двоичных записей простых целых чисел. Доказательство принадлежности $PRIMES$ классу $NP$ разбито на два задания. Часть 1. Известно, что если $n$ простое, то существует $g$, такое что $g^{n-1}=1\pmod n$ и для всех $1 \le k < n - 1$ выполнено $g^k \ne 1 \pmod n$. Пусть известно разложение $n-1$ на простые множители: $n-1=q_1^{a_1}q_2^{a_2}\ldots q_k^{a_k}$. Предложите полиномиальный алгоритм проверки, что заданное $g$ удовлетворяет описанному условию.
 
# $PRIMES\in NP$. Язык $PRIMES$ определяется следующим образом: это множество двоичных записей простых целых чисел. Доказательство принадлежности $PRIMES$ классу $NP$ разбито на два задания. Часть 1. Известно, что если $n$ простое, то существует $g$, такое что $g^{n-1}=1\pmod n$ и для всех $1 \le k < n - 1$ выполнено $g^k \ne 1 \pmod n$. Пусть известно разложение $n-1$ на простые множители: $n-1=q_1^{a_1}q_2^{a_2}\ldots q_k^{a_k}$. Предложите полиномиальный алгоритм проверки, что заданное $g$ удовлетворяет описанному условию.
 
# Часть 2. Можно недетерминированно выбрать $g$ и недетерминированно угадать разбиение $n-1$ на простые множители. Однако это требует проверки на простоту, чтобы убедиться, что угадано разложение именно на простые множители. Завершите доказательство, что $PRIMES \in NP$, описав рекурсивную процедуру проверки и доказав, что она работает за полиномиальное время.
 
# Часть 2. Можно недетерминированно выбрать $g$ и недетерминированно угадать разбиение $n-1$ на простые множители. Однако это требует проверки на простоту, чтобы убедиться, что угадано разложение именно на простые множители. Завершите доказательство, что $PRIMES \in NP$, описав рекурсивную процедуру проверки и доказав, что она работает за полиномиальное время.
# Докажите, что сведение по Карпу не является симметричным отношением на языках.
 
# Докажите, что сведение по Карпу не является антисимметричным отношением на языках.
 
# Задача останова $HALT = \{\langle m, x \rangle | m$ - детерминированная машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
 
# Петя свёл язык $A$ по Карпу к $NP$-полному языку $B$. Учитель утверждает, что из этого не следует, что $A$ является $NP$-полным. Помогите учителю подобрать пример.
 
# Формальная система доказательств представляет собой способ записи утверждений, аксиом, правила вывода и способ записи доказательств. Будем считать, что рассматривается достаточно богатая формальная система, в которой можно записывать различные утверждения про программы. Докажите, что язык $\{\langle \varphi, 1^n\rangle|\varphi$ - верное утверждение, имеющее доказательство длиной не больше $n\}$ является $NP$-трудным. Какие свойства надо предъявить к формальной системе, чтобы он являлся $NP$-полным?
 
# Класс $EXP$ определяется как множество языков $L$, для которых существует детерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Докажите, что $NP \subset EXP$.
 
# Класс $NEXP$ определяется как множество языков $L$, для которых существует недетерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Предложите понятие $NEXP$-полноты. По аналогии с $BH_{1N}$ определите язык $BH_{2N}$, докажите, что он является $NEXP$-полным.
 
# Можно ли сделать альтернативное определение $NEXP$ на языке сертификатов, как мы сделали с $NP$?
 
# Докажите, что если существует язык $L \in NEXPC \cap EXP$, то $NEXP = EXP$.
 
# Предположим, что существует $NP$-полный язык, для которого существует решение за $O(n^{C\log_2n})$, где $C$ - константа. Что можно сказать про класс $NP$ в этом случае?
 
# Рассмотрим языки $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$ и его априорное распределение должно быть как у честной монеты.
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)