Изменения
Нет описания правки
# $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$-полным языком.
# $\Sigma_{i} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p$ — полином $: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}$, где $L$ — формальный язык, $Q$ — подходящий по четности квантор. В частности, $NP = \Sigma_1$. $\Pi_i = co\Sigma_i$. Дайте определение $\Pi_i$ на языке кванторов.
# Докажите, что $\Sigma_i \subset \Sigma_{i+1}$.
# Докажите, что $\Pi_i \subset \Sigma_{i+1}$.
# Докажите, что если $\Sigma_i = \Sigma_{i+1}$, то $\Sigma_{i+1} = \Sigma_{i+2}$.
# Докажите, что если $\Sigma_i = \Pi_i$, то $\Sigma_{i} = \Sigma_{i+1}$.
# $PH = \cup\limits_{i=1}^{\infty}\Sigma_i$. Докажите, что $PH \subset PS$.
# Докажите, что если $PH = PS$, то $PH = \Sigma_i$ для некоторого $i$.
