Теория сложности 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. Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?