Изменения
Нет описания правки
# Будем считать, что $NP \ne coNP$, верно ли, что $coNP \subset DP$?
# Рассмотрим язык $EXACTINDSET = \{\langle G, k\rangle | \text{ максимальное}$ $\text{независимое множество в графе $G$ имеет размер $k$}\}$. Докажите, что $EXACTINDSET$ является полным для класса $DP$ относительно полиномиального сведения.
# Докажите, что $\Sigma_i = co\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}$.
# Докажите, что в любом классе $\Sigma_i$ есть полная задача относительно сведения по Карпу за полином.
# Докажите, что $PH \subset PS$.
# Докажите, что если $P = NP$, то $P = PH$.
# Докажите, что если если у $PH$ существует полный относительно сведения по Карпу за полином язык, то $PH = \Sigma_i$ для некоторого $i$.
# Докажите, что если $PH = PS$, то $PH = \Sigma_i$ для некоторого $i$.
# Докажите, что если $P^A = NP^A$, то $PH^A \subset P^A$.
# Докажите, что $EXACTINDSET \in \Sigma_2$
# Докажите, что $EXACTINDSET \in \Pi_2$
# Сделайте вывод про место $DP$ в полиномиальной иерархии.
