Теория сложности 2019

1. Докажите, что объединение и пересечение языков из $P$ является языком из $P$
2. Докажите, что дополнение языка из $P$ является языком из $P$
3. Докажите, что конкатенация и замыкание Клини языков $P$ является языком из $P$
4. Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
5. Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$
6. Почему рассуждение из задания 2 не применимо к языкам из $NP$?
7. Когда мы задаем числа, мы обычно записываем их в десятичной системе счисления. Докажите, что выбор для формата ввода любой системы счисления с основанием $b \ge 2$ не влияет на принадлежность языка классу $P$.
8. В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $FAC.UNARY = \{\langle 1^n, 1^q \rangle |$ у $n$ существует делитель $t$, такой что $2 \le t \le q < n\}$ лежит в $P$.
9. В унарной системе счисления число $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$.
10. Завершите доказательство, что $PRIMES \in NP$, доказав, суммарный размер рекурсивных сертификатов простоты простых делителей $n-1$ и время на их проверку является полиномом от длины $n$.
11. Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
12. Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
13. Задача реберного покрытия обратных связей $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ - ориентированный граф, который содержит подмножество из $k$ ребер, такое, что любой цикл $G$ содержит хотя бы одно из выбранных ребер $\}$.
14. Задача целочисленного линейного программирования $NP$-полна. Докажите $NP$-полноту следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
15. Задача поиска доминирующего множества $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ либо выбрана, либо имеет выбранного соседа $\}$.
16. Задача пожарных депо. Докажите $NP$-полноту следующего языка. Множество троек $\{\langle G, k, d \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ имеет выбранную вершину на расстоянии не больше $d\}$.
17. Задача о половинной клике. Докажите $NP$-полноту следующего языка. Множество графов $\{G | G$ имеет клику, содержащую ровно половину вершин $G\}$.
18. Задача о раскраске $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k\rangle | G$ имеет правильную раскраску в $k$ цветов $\}$.
19. Задача о раскраске в три цвета $NP$-полна. Докажите $NP$-полноту следующего языка. Множество графов $\{ G | G$ имеет правильную раскраску в три цвета $\}$. Что можно сказать про раскраску в два цвета?
20. Докажите, что задача о гамильтоновом цикле в неориентированном графе $NP$-полна.
21. Докажите, что задача о гамильтоновом пути в ориентированном графе $NP$-полна.
22. Докажите, что задача о гамильтоновом пути в неориентированном графе $NP$-полна.
23. Задача коммивояжера $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{ \langle G, k\rangle | G$ --- взвешенный ориентированный граф, который содержит гамильтонов цикл весом не больше $k \}$.
24. Задача о рюкзаке $NP$-полна. Докажите $NP$-полноту следующего языка. Даны предметы с весом $w_i$ и стоимостью $v_i$. Язык наборов $\{ \langle s, [(v_1, w_1), (v_2, w_2), \ldots (v_n, w_n)], k\rangle | $ можно выбрать предметы с суммарным весом не более $s$ и суммарной стоимостью не менее $k \}$.
25. $PS$-полнота Generalized Geography. Игра в Generalized Geography (GG) ведется на поле, которое представляет собой ориентированный граф с выделенной стартовой вершиной. Исходно фишка находится в стартовой вершине. Два игрока делают ходы по очереди, за один ход игрок перемещает фишку по ребру из текущей вершины. Запрещается перемещать фишку в вершину, где она уже ранее была. Игрок, который не может сделать ход, проигрывает. Докажите, что $GG = \{\langle G, s\rangle|$ первый игрок выигрывает на графе $G$ со стартовой вершиной $s\}$ является $PS$-полным языком.
26. $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$-полным языком.
27. $PS$-полнота языка полных регулярных выражений. Докажите, что $FRE = \{\langle \varphi\rangle|$ любое слово подходит под регулярное выражение $\varphi\}$ является $PS$-полным языком.
28. $\Sigma_{i} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p$ — полином $: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}$, где $L$ — формальный язык, $Q$ — подходящий по четности квантор. В частности, $NP = \Sigma_1$. $\Pi_i = co\Sigma_i$. Дайте определение $\Pi_i$ на языке кванторов.
29. Докажите, что $\Sigma_i \subset \Sigma_{i+1}$.
30. Докажите, что $\Pi_i \subset \Sigma_{i+1}$.
31. Докажите, что если $\Sigma_i = \Sigma_{i+1}$, то $\Sigma_{i+1} = \Sigma_{i+2}$.
32. Докажите, что если $\Sigma_i = \Pi_i$, то $\Sigma_{i} = \Sigma_{i+1}$.
33. Докажите, что в любом классе $\Sigma_i$ есть полная задача относительно сведения по Карпу за полином.
34. $PH = \bigcup\limits_{i=1}^{\infty}\Sigma_i$. Докажите, что $PH \subset PS$.
35. Докажите, что если $PH = PS$, то $PH = \Sigma_i$ для некоторого $i$.
36. Докажите, что если $P^A = NP^A$, то $PH^A \subset P^A$.
37. Докажите, что $2SAT \in NL$
38. Определим $polyL$ как $\cup_{c>0}DSPACE(\log^c n)$. $PATH = \{\langle G, s, t\rangle,$ в ориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $PATH \in polyL$.
39. Определим $SC$ (расшифровывается как Stephen's Class в честь Стивена Кука) как класс языков, для которых существует программа, которая одновременно удовлетворяет ограничениям для $polyL$ и $P$. Неизвестно, принадлежит ли $PATH$ классу $SC$. Поясните, почему доказательство из предыдущего задания не подходит для $SC$.
40. Докажите, что $RP \subset NP$
41. Докажите, что $BPP \subset PP \subset PS$
42. Обозначим как $RL$ класс языков $L$, для которых существует вероятностная программа, которая использует $O(\log n$) памяти и если $x \in L$, то выводит 1 с вероятностью не менее $1/2$, а если $x \not\in L$, то выводит 0. $UPATH = \{\langle G, s, t\rangle,$ в неориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $UPATH \in RL$. Почему это доказательство не работает для $PATH$?
43. Докажите, что $BPP \subset P/poly$.