Теория сложности 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$-полной?