Список заданий по теории сложности 2021

1. Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
2. Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$
3. Когда мы задаем числа, мы обычно записываем их в десятичной системе счисления. Докажите, что выбор для формата ввода любой системы счисления с основанием $b \ge 2$ не влияет на принадлежность языка классу $P$.
4. В унарной системе счисления число $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$.
5. Рассмотрим задачу факторизации: дано число $n$, требуется вывести все простые делители $n$ в неубывающем порядке. Предложите язык $FACT$, такой, что если у нас есть доступ к "черному ящику" для решения $FACT$, можно за полином построить факторизацию числа $n$.
6. Докажите, что язык, построенный в предыдущем задании, $FACT$, если числа в нем задавать в унарной системе счисления, будет лежать в $P$.
7. В заданиях 4 и 6 приведены примеры задания численных значений в унарной системе счисления, чтобы перенести задачу из $NP$ в $P$. Можно ли применить аналогичный трюк для языков $IND$, $CLIQUE$ и $VCOVER$?
8. В определении $NP$ мы говорим, что при любом недетерминированном выборе программа должна завершиться не более чем за $p(n)$, где $p$ - полином, а $n$ - длина входа. На самом деле это требование может быть ослаблено, можно требовать, чтобы программа завершалась не более чем за $p(n)$ только в случае допуска. Докажите, что в таком определении класс $NP$ не меняется.
9. $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$ удовлетворяет описанному условию.
10. Часть 2. Можно недетерминированно выбрать $g$ и недетерминированно угадать разбиение $n-1$ на простые множители. Однако это требует проверки на простоту, чтобы убедиться, что угадано разложение именно на простые множители. Завершите доказательство, что $PRIMES \in NP$, описав рекурсивную процедуру проверки и доказав, что она работает за полиномиальное время.
11. Задача останова $HALT = \{\langle m, x \rangle | m$ - детерминированная машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
12. Докажите, что сведение по Карпу не является антисимметричным отношением на языках.