Изменения
Нет описания правки
# Задача коммивояжера в неориентированном графе. Докажите, что язык $WUHAM = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
# Задача коммивояжера в неориентированном графе без вершин степени 2. Докажите, что язык $WUHAN = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором нет вершин степени 2 и существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
# Докажите, что если $L$ является $NP$-полным, то $\overline{L}$ является $coNP$-полным.
# $TAUT$ - язык булевых формул, любое назначение переменных которым является удовлетворяющим. Докажите, что $TAUT$ является $coNP$-полным.
# Докажите, что если существует язык, который является одновременно $NP$-полным и $coNP$-полным, то $NP = coNP$.
# Докажите, что если $L \le \overline{L}$ и $L$ является $NP$-полным, то $NP = coNP$.
# Пусть языки $L_1$ и $L_2$ принадлежат $NP \cap coNP$. Докажите, что $L_1\oplus L_2$ также принадлежит $NP \cap coNP$.
# Пусть существует односторонняя взаимно однозначная функция: $f : \mathbb{N}\to\mathbb{N}$, преобразующая $n$-битные числа в $n$-битные для любого $n$, причем $f(x)$ можно вычислить за время $poly(n)$, а $f^{-1}(x)$ нельзя вычислить за $poly(n)$ (здесь как $n$ обозначена длина двоичной записи числа $x$). Докажите, что $L=\{(x, y)| f^{-1}(x) < y\}$ лежит в $NP\cap coNP \setminus P$.
# Говорят, что булева формула с кванторами находится в предваренной форме, если сначала идут все кванторы, а затем булева формула: $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$. Докажите, что язык истиных булевых формул с кванторами в предваренной форме является $PS$-полным.
# $PS$-полнота Generalized Geography. Игра в Generalized Geography (GG) ведется на поле, которое представляет собой ориентированный граф с выделенной стартовой вершиной. Исходно фишка находится в стартовой вершине. Два игрока делают ходы по очереди, за один ход игрок перемещает фишку по ребру из текущей вершины. Запрещается перемещать фишку в вершину, где она уже ранее была. Игрок, который не может сделать ход, проигрывает. Докажите, что $GG = \{\langle G, s\rangle|$ первый игрок выигрывает на графе $G$ со стартовой вершиной $s\}$ является $PS$-полным языком.
# $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$-полным языком.
# $PS$-трудность языка полных регулярных выражений. Докажите, что $FRE = \{\langle \varphi\rangle|$ любое слово подходит под регулярное выражение $\varphi\}$ является $PS$-трудным языком.
# Докажите, что $DSPACE(n) \ne NP$.
# Эффективная BGS. Докажите, что существует язык $B \in EXP$, такой что $P^B\ne NP^B$.
