Изменения
Нет описания правки
# Докажите, что $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$.
# Почему решение предыдущей задачи не удается распространить на ориентированные графы?
