Изменения
Нет описания правки
# Докажите, что если $\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$.
# Докажите, что если $P^A = NP^A$, то $PH^A \subset P^A$.
# Докажите, что $2SAT \in NL$
# Определим $polyL$ как $\cup_{c>0}DSPACE(\log^c n)$. $PATH = \{\langle G, s, t\rangle,$ в ориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $PATH \in polyL$.
# Определим $SC$ (расшифровывается как Stephen's Class в честь Стивена Кука) как класс языков, для которых существует программа, которая ''одновременно'' удовлетворяет ограничениям для $polyL$ и $P$. Неизвестно, принадлежит ли $PATH$ классу $SC$. Поясните, почему доказательство из предыдущего задания не подходит для $SC$.
# Докажите, что $RP \subset NP$
# Докажите, что $BPP \subset PP \subset PS$
# Обозначим как $RL$ класс языков $L$, для которых существует вероятностная программа, которая использует $O(\log n$) памяти и если $x \in L$, то выводит 1 с вероятностью не менее $1/2$, а если $x \not\in L$, то выводит 0. $UPATH = \{\langle G, s, t\rangle,$ в неориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $UPATH \in RL$. Почему это доказательство не работает для $PATH$?
# Докажите, что $BPP \subset P/poly$.
