Изменения

Перейти к: навигация, поиск

Теория сложности 2019

179 байт добавлено, 22:31, 7 апреля 2019
Нет описания правки
# Докажите, что если $\Sigma_i = \Sigma_{i+1}$, то $\Sigma_{i+1} = \Sigma_{i+2}$.
# Докажите, что если $\Sigma_i = \Pi_i$, то $\Sigma_{i} = \Sigma_{i+1}$.
# Докажите, что в любом классе $\Sigma_i$ есть полная задача относительно сведения по Карпу за полином.
# $PH = \bigcup\limits_{i=1}^{\infty}\Sigma_i$. Докажите, что $PH \subset PS$.
# Докажите, что если $PH = PS$, то $PH = \Sigma_i$ для некоторого $i$.
Анонимный участник

Навигация