Изменения
Нет описания правки
# Докажите, что если $PH = PS$, то $PH = \Sigma_i$ для некоторого $i$.
# Докажите, что если $P^A = NP^A$, то $PH^A \subset P^A$.
# Докажите, что $EXACTINDSET \in \Sigma_2$ \cup \Pi_2$. Сделайте вывод про место $DP$ в полиномиальной иерархии.
# Адаптируйте доказательство теоремы Фортноу $SAT \not\in TISP(n^c, n^d)$ для любых $c$ и $d$ где $c(c+d) < 2$.
