Изменения
Нет описания правки
# $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$-трудным языком.
# Класс $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$-полным.
# Петя свёл язык $A$ по Карпу к $NP$-полному языку $B$. Учитель утверждает, что из этого не следует, что $A$ является $NP$-полным. Помогите учителю подобрать пример.
# Предположим, что существует $NP$-полный язык, для которого существует решение за $O(n^{C\log_2n})$, где $C$ - константа. Что можно сказать про класс $NP$ в этом случае?
# Верно ли, что если $A \le B$, то $A \in P^B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
# Верно ли, что если $A \in P^B$, то $A \le B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
# Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = NP$. Прокомментируйте определение Серёжи.
# Юра дал такое определение класса $NP$: это задачи, который можно решить перебором. Прокомментируйте определение Юры.
# Докажите, что найдется такой оракул $A$ и язык $L \in NP^A$, что $L$ не сводится к $3SAT$ за полином даже, если у сведения есть доступ к оракулу для $A$.
# Докажите, что если $L\in coNP$, то $L^* \in coNP$.
# Разработайте алгоритм проверки, является ли неориентированный граф, заданный списками смежности, ациклическим, используя $O(\log V)$ дополнительной памяти, где $V$ --- количество вершин графа. Алгоритм должен быть детерминированным.
# Докажите, что $2SAT \in NL$
# $BH_{1N}$ является $NP$-полным. Определите по аналогии $P$-полный язык.
# Определим $polyL$ как $\cup_{c>0}DSPACE(\log^c n)$. $PATH = \{\langle G, s, t\rangle,$ в ориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $PATH \in polyL$.
