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

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. Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
10. Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
11. Задача реберного покрытия обратных связей $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ - ориентированный граф, который содержит подмножество из $k$ ребер, такое, что любой цикл $G$ содержит хотя бы одно из выбранных ребер $\}$.
12. Задача целочисленного линейного программирования $NP$-полна. Докажите $NP$-полноту следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
13. Задача поиска доминирующего множества $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ либо выбрана, либо имеет выбранного соседа $\}$.
14. Задача пожарных депо. Докажите $NP$-полноту следующего языка. Множество троек $\{\langle G, k, d \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ имеет выбранную вершину на расстоянии не больше $d\}$.
15. Задача о половинной клике. Докажите $NP$-полноту следующего языка. Множество графов $\{G | G$ имеет клику, содержащую ровно половину вершин $G\}$.