Список заданий по теории сложности 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$, описав рекурсивную процедуру проверки и доказав, что она работает за полиномиальное время.