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

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