Изменения
Нет описания правки
# Выведите из предыдущего задания, что $NL \subset NC$.
# Докажите, что $L = NC^1$ ($L$ здесь log space).
# Докажите, что $RP \subset BPP$.
# Докажите, что $BPP \subset PS$.
# Докажите, что $RP \subset NP$.
# Обозначим как $PP^+$ как класс языков, для которых существует вероятностная программа $M$, работающая за полином, что если $x \in L$, то $P(M(x) = 1) > 1/2$, а если $x \notin L$, то $P(M(x) = 0) \ge 1/2$. Докажите, что $PP^+ = PP$.
# Докажите, что $NP \subset PP$.
# Докажите, что $RP \subset P/poly$.
# Докажите, что $BPP \subset P/poly$.
# Докажите, что $BPP$ совпадает с классом языков $L$, для которых найдется программа $M$ с полиномиальным временем работы и полином $p$, такие что $P(M(x) = [x \in L]) \ge \frac{1}{2} + \frac{1}{p(|x|)}.$
# Докажите, что $BPP$ совпадает с классом языков $L$, для которых найдется программа $M$ с полиномиальным временем работы и полином $p$, такие что $P(M(x) = [x \in L]) \ge 1 - 2^{-p(|x|)}.$
# Определим класс $RL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log |w|)$ дополнительной памяти, такая что если $x \in L$, то $P(M(x) = 1) \ge 1/2$, если $x \notin L$, то P(M(x) = 1) = 0$. Докажите, что $RL \subset P$
# Докажите, что задача проверки того, что в неориентированном графе есть путь из $s$ в $t$, лежит в $RL$.
# Почему решение предыдущей задачи не удается распространить на ориентированные графы?
