Список заданий по теории сложности 2020 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 9 промежуточных версий 5 участников)
Строка 11: Строка 11:
 
# В заданиях 4-5 приведены примеры задания численных значений в унарной системе счисления, чтобы перенести задачу из $NP$ в $P$. Можно ли применить аналогичный трюк в задачах 6-9?  
 
# В заданиях 4-5 приведены примеры задания численных значений в унарной системе счисления, чтобы перенести задачу из $NP$ в $P$. Можно ли применить аналогичный трюк в задачах 6-9?  
 
# В определении $NP$ мы говорим, что при любом недетерминированном выборе программа должна завершиться не более чем за $p(n)$, где $p$ - полином, а $n$ - длина входа. На самом деле это требование может быть ослаблено, можно требовать, чтобы программа завершалась не более чем за $p(n)$ только в случае допуска. Докажите, что в таком определении класс $NP$ не меняется.
 
# В определении $NP$ мы говорим, что при любом недетерминированном выборе программа должна завершиться не более чем за $p(n)$, где $p$ - полином, а $n$ - длина входа. На самом деле это требование может быть ослаблено, можно требовать, чтобы программа завершалась не более чем за $p(n)$ только в случае допуска. Докажите, что в таком определении класс $NP$ не меняется.
# $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$-полной?
 +
# Докажите, что сведение по Карпу не является симметричным отношением на языках.
 +
# Докажите, что сведение по Карпу не является антисимметричным отношением на языках.
 +
# Докажите, что если существует язык $L \in NPC \cap P$, то $NP = P$.
 +
# Формальная система доказательств представляет собой способ записи утверждений, аксиом, правила вывода и способ записи доказательств. Будем считать, что рассматривается достаточно богатая формальная система, в которой можно записывать различные утверждения про программы. Докажите, что язык $\{\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$.
 +
# Пусть задан язык $L$, принадлежащий $NP$. Зафиксируем проверку сертификатов $R(x, y)$. Обозначим как $c(x)$ число сертификатов, которые подходят для данного $x$ (очевидно, если $x \not\in L$, то $c(x) = 0$, а если $x \in L$, то $c(x) \ge 1$). Сведение по Карпу $f$ одного языка к другому, для каждого из которых зафиксирована проверка сертификатов, называется честным (англ. parsimonious), если оно сохраняет $c$, то есть $c(f(x)) = c(x)$. Докажите, что сведение $BH_{1N}$ к $SAT$ в теореме Кука является честным, если в качестве сертификата использовать последовательность недетерминированных выборов, приводящих машину Тьюринга из входа для $BH_{1N}$ к допуску.
 +
# Верно ли, что если $A \le B$, то $A \in P^B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
 +
# Верно ли, что если $A \in P^B$, то $A \le B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
 +
# Предположим, что существует $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$ на основании этого?
 +
# Петя свёл язык $A$ по Карпу к $NP$-полному языку $B$. Учитель утверждает, что из этого не следует, что $A$ является $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$-трудность следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
 +
# Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = 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$-полным.
 +
# Докажите, что если $L$ является $NP$-полным, то $\overline{L}$ является $coNP$-полным.
 +
# $TAUT$ - язык булевых формул, любое назначение переменных которым является удовлетворяющим. Докажите, что $TAUT$ является $coNP$-полным.
 +
# Докажите, что если существует язык, который является одновременно $NP$-полным и $coNP$-полным, то $NP = coNP$.
 +
# Докажите, что если $L \le \overline{L}$ и $L$ является $NP$-полным, то $NP = coNP$.
 +
# Пусть языки $L_1$ и $L_2$ принадлежат $NP \cap coNP$. Докажите, что $L_1\oplus L_2$ также принадлежит $NP \cap coNP$.
 +
# Пусть существует односторонняя взаимно однозначная функция: $f : \mathbb{N}\to\mathbb{N}$, преобразующая $n$-битные числа в $n$-битные для любого $n$, причем $f(x)$ можно вычислить за время $poly(n)$, а $f^{-1}(x)$ нельзя вычислить за $poly(n)$ (здесь как $n$ обозначена длина двоичной записи числа $x$). Докажите, что $L=\{(x, y)| f^{-1}(x) < y\}$ лежит в $NP\cap coNP \setminus P$.
 +
# Говорят, что булева формула с кванторами находится в предваренной форме, если сначала идут все кванторы, а затем булева формула: $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$. Докажите, что язык истиных булевых формул с кванторами в предваренной форме является $PS$-полным.
 +
# $PS$-полнота Generalized Geography. Игра в Generalized Geography (GG) ведется на поле, которое представляет собой ориентированный граф с выделенной стартовой вершиной. Исходно фишка находится в стартовой вершине. Два игрока делают ходы по очереди, за один ход игрок перемещает фишку по ребру из текущей вершины. Запрещается перемещать фишку в вершину, где она уже ранее была. Игрок, который не может сделать ход, проигрывает. Докажите, что $GG = \{\langle G, s\rangle|$ первый игрок выигрывает на графе $G$ со стартовой вершиной $s\}$ является $PS$-полным языком.
 +
# $PS$-полнота Shannon Switching Game. Игра Шеннона ведется на поле, которое представляет собой неориентированный граф с двумя выделенными вершинами $s$ и $t$. Два игрока Short и Cut делают ходы по очереди, Short ходит первым. За один ход Short может выбрать одну вершину и защитить её. За один ход Cut может удалить любую вершину, кроме $s$, $t$ и защищенных к текущему моменту вершин. В конце Short выигрывает, если по защищенным вершинам можно добраться от $s$ до $t$. Докажите, что $SHSW = \{\langle G, s, t\rangle|$ Short выигрывает на графе $G$ с выделенными вершиными $s$ и $t\}$ является $PS$-полным языком.
 +
# $PS$-трудность языка полных регулярных выражений. Докажите, что $FRE = \{\langle \varphi\rangle|$ любое слово подходит под регулярное выражение $\varphi\}$ является $PS$-трудным языком.
 +
# Докажите, что $DSPACE(n) \ne NP$.
 +
# Эффективная BGS. Докажите, что существует язык $B \in EXP$, такой что $P^B\ne NP^B$.

Текущая версия на 16:23, 28 марта 2020

  1. Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
  2. Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$
  3. Когда мы задаем числа, мы обычно записываем их в десятичной системе счисления. Докажите, что выбор для формата ввода любой системы счисления с основанием $b \ge 2$ не влияет на принадлежность языка классу $P$.
  4. В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $FAC.UNARY = \{\langle 1^n, 1^q \rangle |$ у $n$ существует делитель $t$, такой что $2 \le t \le q < n\}$ лежит в $P$. Что можно сказать про аналогичную задачу, где ввод задается в двоичной системе счисления?
  5. В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $UNARY.SUBSET.SUM = \{\langle 1^s, [1^{a_1}, 1^{a_2}, \ldots, 1^{a_n}] \rangle |$ можно выбрать подмножество $\{a_1, a_2,\ldots, a_n\}$ с суммой $s\}$ лежит в $P$.
  6. Язык $IND$ определяется следующим образом: $IND = \{\langle G, k\rangle|\mbox{в графе $G$ есть независимое множество размера $k$}\}$. Докажите, что $IND\in NP$.
  7. Язык $CLIQUE$ определяется следующим образом: $CLIQUE = \{\langle G, k\rangle|\mbox{в графе $G$ есть клика размера $k$}\}$. Докажите, что $CLIQUE\in NP$.
  8. Язык $VCOVER$ определяется следующим образом: $VCOVER = \{\langle G, k\rangle|\mbox{в графе $G$ есть вершинное покрытие размера $k$}\}$. Докажите, что $VCOVER\in NP$.
  9. Язык $COL$ определяется следующим образом: $COL = \{\langle G, k\rangle|\mbox{в графе $G$ есть раскраска в $k$ цветов}\}$. Докажите, что $COL\in NP$.
  10. Об оптимизации и проверке предиката. В предыдущих четырех заданиях гораздо логичнее было бы спросить "какой максимальный размер независимого множества в графе", "какое минимальное вершинное покрытие в графе", "в какое минимальное число цветов можно раскрасить граф". Аргументируйте, что постановка в формате проверки предиката с точки зрения полиномиальной разрешимости не хуже.
  11. В заданиях 4-5 приведены примеры задания численных значений в унарной системе счисления, чтобы перенести задачу из $NP$ в $P$. Можно ли применить аналогичный трюк в задачах 6-9?
  12. В определении $NP$ мы говорим, что при любом недетерминированном выборе программа должна завершиться не более чем за $p(n)$, где $p$ - полином, а $n$ - длина входа. На самом деле это требование может быть ослаблено, можно требовать, чтобы программа завершалась не более чем за $p(n)$ только в случае допуска. Докажите, что в таком определении класс $NP$ не меняется.
  13. $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$ удовлетворяет описанному условию.
  14. Часть 2. Можно недетерминированно выбрать $g$ и недетерминированно угадать разбиение $n-1$ на простые множители. Однако это требует проверки на простоту, чтобы убедиться, что угадано разложение именно на простые множители. Завершите доказательство, что $PRIMES \in NP$, описав рекурсивную процедуру проверки и доказав, что она работает за полиномиальное время.
  15. Задача останова $HALT = \{\langle m, x \rangle | m$ - детерминированная машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
  16. Докажите, что сведение по Карпу не является симметричным отношением на языках.
  17. Докажите, что сведение по Карпу не является антисимметричным отношением на языках.
  18. Докажите, что если существует язык $L \in NPC \cap P$, то $NP = P$.
  19. Формальная система доказательств представляет собой способ записи утверждений, аксиом, правила вывода и способ записи доказательств. Будем считать, что рассматривается достаточно богатая формальная система, в которой можно записывать различные утверждения про программы. Докажите, что язык $\{\langle \varphi, 1^n\rangle|\varphi$ - верное утверждение, имеющее доказательство длиной не больше $n\}$ является $NP$-трудным. Какие свойства надо предъявить к формальной системе, чтобы он являлся $NP$-полным?
  20. Класс $EXP$ определяется как множество языков $L$, для которых существует детерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Докажите, что $NP \subset EXP$.
  21. Класс $NEXP$ определяется как множество языков $L$, для которых существует недетерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Предложите понятие $NEXP$-полноты. По аналогии с $BH_{1N}$ определите язык $BH_{2N}$, докажите, что он является $NEXP$-полным.
  22. Можно ли сделать альтернативное определение $NEXP$ на языке сертификатов, как мы сделали с $NP$?
  23. Докажите, что если существует язык $L \in NEXPC \cap EXP$, то $NEXP = EXP$.
  24. Пусть задан язык $L$, принадлежащий $NP$. Зафиксируем проверку сертификатов $R(x, y)$. Обозначим как $c(x)$ число сертификатов, которые подходят для данного $x$ (очевидно, если $x \not\in L$, то $c(x) = 0$, а если $x \in L$, то $c(x) \ge 1$). Сведение по Карпу $f$ одного языка к другому, для каждого из которых зафиксирована проверка сертификатов, называется честным (англ. parsimonious), если оно сохраняет $c$, то есть $c(f(x)) = c(x)$. Докажите, что сведение $BH_{1N}$ к $SAT$ в теореме Кука является честным, если в качестве сертификата использовать последовательность недетерминированных выборов, приводящих машину Тьюринга из входа для $BH_{1N}$ к допуску.
  25. Верно ли, что если $A \le B$, то $A \in P^B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
  26. Верно ли, что если $A \in P^B$, то $A \le B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
  27. Предположим, что существует $NP$-полный язык, для которого существует решение за $O(n^{C\log_2n})$, где $C$ - константа. Что можно сказать про класс $NP$ в этом случае?
  28. Рассмотрим языки $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$ на основании этого?
  29. Петя свёл язык $A$ по Карпу к $NP$-полному языку $B$. Учитель утверждает, что из этого не следует, что $A$ является $NP$-полным. Помогите учителю подобрать пример.
  30. Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
  31. Задача о покрытии подмножествами $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$ лежал хотя бы в одном выбранном множестве $\}$.
  32. Задача реберного покрытия обратных связей $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ - ориентированный граф, который содержит подмножество из $k$ ребер, такое, что любой цикл $G$ содержит хотя бы одно из выбранных ребер $\}$.
  33. Задача поиска доминирующего множества $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $DOM = \{\langle G, k \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ либо выбрана, либо имеет выбранного соседа $\}$.
  34. Задача пожарных депо. Докажите $NP$-полноту следующего языка. Множество троек $\{\langle G, k, d \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ имеет выбранную вершину на расстоянии не больше $d\}$.
  35. Задача о половинной клике. Докажите $NP$-полноту следующего языка. Множество графов $HALFCLIQUE=\{G | G$ имеет клику, содержащую ровно половину вершин $G\}$.
  36. Задача о раскраске $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $COL=\{\langle G, k\rangle | G$ имеет правильную раскраску в $k$ цветов $\}$.
  37. Задача о раскраске в три цвета $NP$-полна. Докажите $NP$-полноту следующего языка. Множество графов $3COL=\{ G | G$ имеет правильную раскраску в три цвета $\}$. Что можно сказать про раскраску в два цвета?
  38. Задача о рюкзаке $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 \}$.
  39. Задача целочисленного линейного программирования $NP$-трудна. Докажите $NP$-трудность следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
  40. Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = NP$. Прокомментируйте определение Серёжи.
  41. Юра дал такое определение класса $NP$: это задачи, который можно решить перебором. Прокомментируйте определение Юры.
  42. Неориентированный гамильтонов цикл. Докажите, что язык $UHAM = \{G | G$ - неориентированный граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
  43. Ориентированный гамильтонов путь. Докажите, что язык $HAMP = \{G | G$ - ориентированный граф, содержащий гамильтонов путь$\}$ является $NP$-полным.
  44. Неориентированный гамильтонов путь. Докажите, что язык $UHAMP = \{G | G$ - неориентированный граф, содержащий гамильтонов путь$\}$ является $NP$-полным.
  45. Выполните явное взаимное сведение языка $HAM = \{G | G$ - ориентированный граф, содержащий гамильтонов цикл$\}$ и языков из предыдущих трех заданий, не обращаясь к общим теоремам типа теоремы Кука.
  46. Неориентированный планарный гамильтонов цикл. Докажите, что язык $PUHAM = \{G | G$ - неориентированный планарный граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
  47. Неориентированный гамильтонов цикл в кубическом графе. Докажите, что язык $CUHAM = \{G | G$ - неориентированный кубический граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
  48. Неориентированный гамильтонов цикл в почти кубическом планарном графе. Докажите, что язык $CPUHAM = \{G | G$ - неориентированный планарный граф, степени вершин которого не превышают 3, содержащий гамильтонов цикл$\}$ является $NP$-полным.
  49. Задача коммивояжера. Докажите, что язык $WHAM = \{\langle G, w\rangle | G $ - взвешенный ориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
  50. Задача коммивояжера в неориентированном графе. Докажите, что язык $WUHAM = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
  51. Задача коммивояжера в неориентированном графе без вершин степени 2. Докажите, что язык $WUHAN = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором нет вершин степени 2 и существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
  52. Докажите, что если $L$ является $NP$-полным, то $\overline{L}$ является $coNP$-полным.
  53. $TAUT$ - язык булевых формул, любое назначение переменных которым является удовлетворяющим. Докажите, что $TAUT$ является $coNP$-полным.
  54. Докажите, что если существует язык, который является одновременно $NP$-полным и $coNP$-полным, то $NP = coNP$.
  55. Докажите, что если $L \le \overline{L}$ и $L$ является $NP$-полным, то $NP = coNP$.
  56. Пусть языки $L_1$ и $L_2$ принадлежат $NP \cap coNP$. Докажите, что $L_1\oplus L_2$ также принадлежит $NP \cap coNP$.
  57. Пусть существует односторонняя взаимно однозначная функция: $f : \mathbb{N}\to\mathbb{N}$, преобразующая $n$-битные числа в $n$-битные для любого $n$, причем $f(x)$ можно вычислить за время $poly(n)$, а $f^{-1}(x)$ нельзя вычислить за $poly(n)$ (здесь как $n$ обозначена длина двоичной записи числа $x$). Докажите, что $L=\{(x, y)| f^{-1}(x) < y\}$ лежит в $NP\cap coNP \setminus P$.
  58. Говорят, что булева формула с кванторами находится в предваренной форме, если сначала идут все кванторы, а затем булева формула: $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$. Докажите, что язык истиных булевых формул с кванторами в предваренной форме является $PS$-полным.
  59. $PS$-полнота Generalized Geography. Игра в Generalized Geography (GG) ведется на поле, которое представляет собой ориентированный граф с выделенной стартовой вершиной. Исходно фишка находится в стартовой вершине. Два игрока делают ходы по очереди, за один ход игрок перемещает фишку по ребру из текущей вершины. Запрещается перемещать фишку в вершину, где она уже ранее была. Игрок, который не может сделать ход, проигрывает. Докажите, что $GG = \{\langle G, s\rangle|$ первый игрок выигрывает на графе $G$ со стартовой вершиной $s\}$ является $PS$-полным языком.
  60. $PS$-полнота Shannon Switching Game. Игра Шеннона ведется на поле, которое представляет собой неориентированный граф с двумя выделенными вершинами $s$ и $t$. Два игрока Short и Cut делают ходы по очереди, Short ходит первым. За один ход Short может выбрать одну вершину и защитить её. За один ход Cut может удалить любую вершину, кроме $s$, $t$ и защищенных к текущему моменту вершин. В конце Short выигрывает, если по защищенным вершинам можно добраться от $s$ до $t$. Докажите, что $SHSW = \{\langle G, s, t\rangle|$ Short выигрывает на графе $G$ с выделенными вершиными $s$ и $t\}$ является $PS$-полным языком.
  61. $PS$-трудность языка полных регулярных выражений. Докажите, что $FRE = \{\langle \varphi\rangle|$ любое слово подходит под регулярное выражение $\varphi\}$ является $PS$-трудным языком.
  62. Докажите, что $DSPACE(n) \ne NP$.
  63. Эффективная BGS. Докажите, что существует язык $B \in EXP$, такой что $P^B\ne NP^B$.