244
правки
Изменения
Нет описания правки
# Задача коммивояжера в неориентированном графе. Докажите, что язык $WUHAM = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
# Задача коммивояжера в неориентированном графе без вершин степени 2. Докажите, что язык $WUHAN = \{\langle G, w\rangle | G $ - взвешенный неориентированный граф, в котором нет вершин степени 2 и существует гамильтонов путь длины не более $w \}$ является $NP$-полным.
# Говорят, что булева формула с кванторами находится в предваренной форме, если сначала идут все кванторы, а затем булева формула: $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$. Докажите, что язык истиных булевых формул с кванторами в предваренной форме является $PS$-полным.
# Говорят, что булева формула с кванторами находится в КНФ, если она находится в предваренной форме $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$, причём $\varphi$ находится в КНФ. Докажите, что язык истиных булевых формул с кванторами в КНФ является $PS$-полным.
# Говорят, что булева формула с кванторами находится в 3-КНФ, если она находится в предваренной форме $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$, причём $\varphi$ находится в 3-КНФ. Докажите, что язык истиных булевых формул с кванторами в 3-КНФ является $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$-полным языком.
# Класс $EXP$ определяется как множество языков $L$, для которых существует детерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Докажите, что $NP \subset EXP$.
# Класс $NEXP$ определяется как множество языков $L$, для которых существует недетерминированная программа, разрешающая $L$ за $O(2^{p(n)})$, где $p(n)$ - полином. Предложите понятие $NEXP$-полноты. По аналогии с $BH_{1N}$ определите язык $BH_{2N}$, докажите, что он является $NEXP$-полным.
# Можно ли сделать альтернативное определение $NEXP$ на языке сертификатов, как мы сделали с $NP$?
# Докажите, что если существует язык $L \in NEXPC \cap EXP$, то $NEXP = EXP$.
# Пусть задан язык $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}$ к допуску.
