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

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$-полной?
11. Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
12. Задача о покрытии подмножествами $NP$-полна. Докажите $NP$-полноту следующего языка. Даны $n$ множеств $S_i\subset\{1, 2, \ldots, m\}$ и число $k$. Язык наборов $SETCOVER = \{ \langle [S_1, S_2, \ldots, S_n], k\rangle$ можно выбрать не более $k$ множеств, чтобы каждый элемент от $1$ до $m$ лежал хотя бы в одном выбранном множестве $\}$.
13. Задача реберного покрытия обратных связей $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ - ориентированный граф, который содержит подмножество из $k$ ребер, такое, что любой цикл $G$ содержит хотя бы одно из выбранных ребер $\}$.
14. Задача поиска доминирующего множества $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $DOM = \{\langle G, k \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ либо выбрана, либо имеет выбранного соседа $\}$.
15. Задача пожарных депо. Докажите $NP$-полноту следующего языка. Множество троек $\{\langle G, k, d \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ имеет выбранную вершину на расстоянии не больше $d\}$.
16. Задача о половинной клике. Докажите $NP$-полноту следующего языка. Множество графов $HALFCLIQUE=\{G | G$ имеет клику, содержащую ровно половину вершин $G\}$.
17. Задача о раскраске в три цвета $NP$-полна. Докажите $NP$-полноту следующего языка. Множество графов $3COL=\{ G | G$ имеет правильную раскраску в три цвета $\}$. Что можно сказать про раскраску в два цвета?
18. Задача о рюкзаке $NP$-полна. Докажите $NP$-полноту следующего языка. Даны предметы с весом $w_i$ и стоимостью $v_i$. Язык наборов $KNAPSACK=\{ \langle s, [(v_1, w_1), (v_2, w_2), \ldots (v_n, w_n)], k\rangle | $ можно выбрать предметы с суммарным весом не более $s$ и суммарной стоимостью не менее $k \}$.
19. Неориентированный гамильтонов цикл. Докажите, что язык $UHAM = \{G | G$ - неориентированный граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
20. Ориентированный гамильтонов путь. Докажите, что язык $HAMP = \{G | G$ - ориентированный граф, содержащий гамильтонов путь$\}$ является $NP$-полным.
21. Неориентированный гамильтонов путь. Докажите, что язык $UHAMP = \{G | G$ - неориентированный граф, содержащий гамильтонов путь$\}$ является $NP$-полным.
22. Неориентированный планарный гамильтонов цикл. Докажите, что язык $PUHAM = \{G | G$ - неориентированный планарный граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
23. Неориентированный гамильтонов цикл в кубическом графе. Докажите, что язык $CUHAM = \{G | G$ - неориентированный кубический граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
24. Неориентированный гамильтонов цикл в почти кубическом планарном графе. Докажите, что язык $CPUHAM = \{G | G$ - неориентированный планарный граф, степени вершин которого не превышают 3, содержащий гамильтонов цикл$\}$ является $NP$-полным.
25. Задача коммивояжера. Докажите, что язык $WHAM = \{\langle G, w\rangle | G $ - взвешенный ориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
26. Задача коммивояжера в неориентированном графе. Докажите, что язык $WUHAM = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
27. Задача коммивояжера в неориентированном графе без вершин степени 2. Докажите, что язык $WUHAN = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором нет вершин степени 2 и существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
28. Говорят, что булева формула с кванторами находится в предваренной форме, если сначала идут все кванторы, а затем булева формула: $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$. Докажите, что язык истиных булевых формул с кванторами в предваренной форме является $PS$-полным.
29. Говорят, что булева формула с кванторами находится в КНФ, если она находится в предваренной форме $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$, причём $\varphi$ находится в КНФ. Докажите, что язык истиных булевых формул с кванторами в КНФ является $PS$-полным.
30. Говорят, что булева формула с кванторами находится в 3-КНФ, если она находится в предваренной форме $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$, причём $\varphi$ находится в 3-КНФ. Докажите, что язык истиных булевых формул с кванторами в 3-КНФ является $PS$-полным.
31. $PS$-полнота Generalized Geography. Игра в Generalized Geography (GG) ведется на поле, которое представляет собой ориентированный граф с выделенной стартовой вершиной. Исходно фишка находится в стартовой вершине. Два игрока делают ходы по очереди, за один ход игрок перемещает фишку по ребру из текущей вершины. Запрещается перемещать фишку в вершину, где она уже ранее была. Игрок, который не может сделать ход, проигрывает. Докажите, что $GG = \{\langle G, s\rangle|$ первый игрок выигрывает на графе $G$ со стартовой вершиной $s\}$ является $PS$-полным языком.
32. $PS$-полнота Shannon Switching Game. Игра Шеннона ведется на поле, которое представляет собой неориентированный граф с двумя выделенными вершинами $s$ и $t$. Два игрока Short и Cut делают ходы по очереди, Short ходит первым. За один ход Short может выбрать одну вершину и защитить её. За один ход Cut может удалить любую вершину, кроме $s$, $t$ и защищенных к текущему моменту вершин. В конце Short выигрывает, если по защищенным вершинам можно добраться от $s$ до $t$. Докажите, что $SHSW = \{\langle G, s, t\rangle|$ Short выигрывает на графе $G$ с выделенными вершиными $s$ и $t\}$ является $PS$-полным языком.
33. Класс $EXP$ определяется как множество языков $L$, для которых существует детерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Докажите, что $NP \subset EXP$.
34. Класс $NEXP$ определяется как множество языков $L$, для которых существует недетерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Предложите понятие $NEXP$-полноты. По аналогии с $BH_{1N}$ определите язык $BH_{2N}$, докажите, что он является $NEXP$-полным.
35. Можно ли сделать альтернативное определение $NEXP$ на языке сертификатов, как мы сделали с $NP$?
36. Докажите, что если существует язык $L \in NEXPC \cap EXP$, то $NEXP = EXP$.
37. Пусть задан язык $L$, принадлежащий $NP$. Зафиксируем проверку сертификатов $R(x, y)$. Обозначим как $c(x)$ число сертификатов, которые подходят для данного $x$ (очевидно, если $x \not\in L$, то $c(x) = 0$, а если $x \in L$, то $c(x) \ge 1$). Сведение по Карпу $f$ одного языка к другому, для каждого из которых зафиксирована проверка сертификатов, называется честным (англ. parsimonious), если оно сохраняет $c$, то есть $c(f(x)) = c(x)$. Докажите, что сведение $BH_{1N}$ к $SAT$ в теореме Кука является честным, если в качестве сертификата использовать последовательность недетерминированных выборов, приводящих машину Тьюринга из входа для $BH_{1N}$ к допуску.
38. Эффективная BGS. Докажите, что существует язык $B \in EXP$, такой что $P^B\ne NP^B$.
39. Докажите, что $DSPACE(n) \ne NP$.
40. Формальная система доказательств представляет собой способ записи утверждений, аксиом, правила вывода и способ записи доказательств. Будем считать, что рассматривается достаточно богатая формальная система, в которой можно записывать различные утверждения про программы. Докажите, что язык $\{\langle \varphi, 1^n\rangle|\varphi$ - верное утверждение, имеющее доказательство длиной не больше $n\}$ является $NP$-трудным. Какие свойства надо предъявить к формальной системе, чтобы он являлся $NP$-полным?
41. Петя свёл язык $A$ по Карпу к $NP$-полному языку $B$. Учитель утверждает, что из этого не следует, что $A$ является $NP$-полным. Помогите учителю подобрать пример.
42. Предположим, что существует $NP$-полный язык, для которого существует решение за $O(n^{C\log_2n})$, где $C$ - константа. Что можно сказать про класс $NP$ в этом случае?
43. Верно ли, что если $A \le B$, то $A \in P^B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
44. Верно ли, что если $A \in P^B$, то $A \le B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
45. Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = NP$. Прокомментируйте определение Серёжи.
46. Юра дал такое определение класса $NP$: это задачи, который можно решить перебором. Прокомментируйте определение Юры.
47. Докажите, что найдется такой оракул $A$ и язык $L \in NP^A$, что $L$ не сводится к $3SAT$ за полином даже, если у сведения есть доступ к оракулу для $A$.
48. Докажите, что если $L\in coNP$, то $L^* \in coNP$.
49. Покажите, что $TQBF$ является $PS$-трудной даже для $LOG-Space$ сведений.
50. Может ли выполняться $TQBF\in L$?
51. Может ли выполняться $TQBF\in NL$?
52. Разработайте алгоритм, который по матрице смежности графа выводит его матрицу инцидентности, используя $O(\log V)$ дополнительной памяти, где $V$ --- количество вершин графа.
53. Разработайте алгоритм проверки, является ли неориентированный граф, заданный списками смежности, ациклическим, используя $O(\log V)$ дополнительной памяти, где $V$ --- количество вершин графа. Алгоритм должен быть детерминированным.
54. Разработайте недетерминированный алгоритм проверки, является ли ориентированный граф, заданный списками смежности, ациклическим, используя $O(\log V)$ дополнительной памяти, где $V$ --- количество вершин графа.
55. Докажите, что $2SAT \in NL$
56. $BH_{1N}$ является $NP$-полным. Определите по аналогии $P$-полный язык.
57. Определим $polyL$ как $\cup_{c>0}DSPACE(\log^c n)$. $PATH = \{\langle G, s, t\rangle,$ в ориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $PATH \in polyL$.
58. Определим $SC$ (расшифровывается как Stephen's Class в честь Стивена Кука) как класс языков, для которых существует программа, которая одновременно удовлетворяет ограничениям для $polyL$ и $P$. Неизвестно, принадлежит ли $PATH$ классу $SC$. Поясните, почему доказательство из предыдущего задания не подходит для $SC$.
59. Обозначим как $DP$ множество языков $L$, для которых найдутся $L_1 \in NP$ и $L_2 \in coNP$, такие что $L = L_1 \cap L_2$. Докажите, что $NP \subset DP$.
60. Будем считать, что $NP \ne coNP$, верно ли, что $coNP \subset DP$?
61. Рассмотрим язык $EXACTINDSET = \{\langle G, k\rangle | \text{ максимальное}$ $\text{независимое множество в графе $G$ имеет размер $k$}\}$. Докажите, что $EXACTINDSET$ является полным для класса $DP$ относительно полиномиального сведения.
62. Докажите, что если $\Sigma_i = \Pi_i$, то $\Sigma_{i} = \Sigma_{i+1}$.
63. Докажите, что $\Sigma_{i+1} = NP^{\Sigma_i}$.
64. Задайте $\Pi_{i+1}$ через классы $i$-го уровня $PH$ на языке оракулов.
65. Докажите, что если $P = NP$, то $P = PH$.
66. Докажите, что если если у $PH$ существует полный относительно сведения по Карпу за полином язык, то $PH = \Sigma_i$ для некоторого $i$.
67. Докажите, что если $PH = PS$, то $PH = \Sigma_i$ для некоторого $i$.
68. Докажите, что если $P^A = NP^A$, то $PH^A \subset P^A$.
69. Докажите, что $EXACTINDSET \in \Sigma_2 \cup \Pi_2$. Сделайте вывод про место $DP$ в полиномиальной иерархии.
70. Адаптируйте доказательство теоремы Фортноу $SAT \not\in TISP(n^c, n^d)$ для любых $c$ и $d$ где $c(c+d) < 2$.
71. Докажите, что задача $CIRCSAT$ о проверке удовлетворимости булевой схемы из функциональных элементов является $NP$-полной.
72. Предложите разрешимый язык из $P/poly$, который не лежит в $P$.
73. Докажите, что $Sparse \subset P/poly$ ($Sparse$ - множество языков, которые имеют лишь полиномиальное число слов каждой длины).
74. Докажите, что для любого $k > 0$ в $PH$ найдется язык, со схемной сложностью $\Omega(n^k)$.
75. Докажите, что для любого $k > 0$ в $\Sigma_2$ найдется язык, со схемной сложностью $\Omega(n^k)$.
76. Докажите, что существует язык из $DSPACE(2^{O(n)})$, которой не принадлежит $SIZE(2^{o(n)})$.
77. Докажите, что если $EXP \subset P/poly$, то $EXP = \Sigma_2$.
78. Докажите, что если $P=NP$, то в $EXP$, есть язык со схемной сложностью $\Omega(2^n/n)$.
79. Докажите, что умножение булевых матриц лежит в $NC$ (иначе говоря, существует схема глубиной $\log^k(n)$ для умножения матриц $n \times n$ для некоторой константы $k$).
80. Выведите из предыдущего задания, что $PATH \in NC$.
81. Выведите из предыдущего задания, что $NL \subset NC$.
82. Докажите, что $NC^1 \subset L$ ($L$ здесь log space).
83. Докажите, что $BPP \subset PS$.
84. Обозначим как $PP^+$ как класс языков, для которых существует вероятностная программа $M$, работающая за полином, что если $x \in L$, то $P(M(x) = 1) > 1/2$, а если $x \notin L$, то $P(M(x) = 0) \ge 1/2$. Докажите, что $PP^+ = PP$.
85. Докажите, что $NP \subset PP$.
86. Докажите, что если для $L$ найдется программа $M$ с полиномиальным временем работы и полином $p > 0$, такие что $P(M(x) = [x \in L]) \ge \frac{1}{2} + \frac{1}{p(|x|)}$, то $L \in BPP$.
87. Докажите, что если $L \in BPP$, то для любого полинома $p > 1$ найдется программа $M$ с полиномиальным временем работы, такая что $P(M(x) = [x \in L]) \ge 1 - 2^{-p(|x|)}.$
88. Определим класс $RL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $x \in L$, то $P(M(x) = 1) \ge 1/2$, если $x \notin L$, то $P(M(x) = 1) = 0$. Докажите, что $RL \subset P$
89. Докажите, что задача проверки того, что в неориентированном графе есть путь из $s$ в $t$, лежит в $RL$.
90. Почему решение предыдущей задачи не удается распространить на ориентированные графы?
91. Докажите, что если $NP \subset BPP$, то $NP = RP$.
92. В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.
93. При симуляции $random(n)$ с помощью бросков честной монеты (или абстракции вероятностной ленты) математическое ожидание времени работы $random(n)$ равно $O(\log n)$, но нет ограничения сверху на число бросков. Кажется, что это может испортить определение классов $RP$ или $BPP$, потому что в них время работы программы должно быть ограничено сверху. Докажите, что это не так и можно разрешить конструкции $random(n)$ в вероятностных программах из определения $RP$ или $BPP$, даже если на самом деле в модели вычислений есть доступ к источнику случайности только с распределением честной монеты.
94. Нечестные монеты с нерациональным $p$ могут привести к парадоксам. Докажите, что существует такое $p$, такой неразрешимый язык $L$ и такая программа $A$, что если у программы $A$ есть доступ к источнику случайности с распределением нечестной монеты с вероятностью выпадения $1$ равной $p$, то она может распознать язык $L$ за полиномиальное время.
95. Полные языки для $BPP$. Будем называть $A\in BPP$ язык полным для $BPP$, если для любого языка $B \in BPP$ выполнено $B \le A$. Петя предполагает, что язык $BH_{1DP} = \{\langle p, x, 1^t \rangle\}$, где $p$ — вероятностная программа, допускающая $x$ за время $t$ с вероятностью не меньше $2/3$ является полным для $BPP$. Прав ли Петя?
96. Вероятностные сведения. Будем говорить, что $B$ вероятностно сводится к $C$ и писать $B \le_r C$, если найдется такая вероятностная программа $p$, работающая за полином, что $P([x \in B] = [p(x) \in C]) \ge 2/3$. Докажите, что если $C \in BPP$, $B \le_r C$, то $B \in BPP$.
97. Докажите, что $\le_r$ не является транзитивным отношением.
98. Класс $BP\cdot NP$ определяется как множество $\{A | A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.
99. Докажите, что $BPP \subset BP\cdot NP$.
100. Докажите, что $BP\cdot NP \subset \Sigma_3$.
101. Докажите, что если $\overline{3SAT} \subset BP\cdot NP$, то $PH = \Sigma_3$.
102. Определим класс $BPL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $P(M(x) = [x \in L]) \ge 2/3$. Докажите, что $BPL \subset P$.
103. Докажите, что $BPL \subset SC$.