Изменения
Нет описания правки
# Выведите из предыдущего задания, что $NL \subset NC$.
# Докажите, что $NC^1 \subset L$ ($L$ здесь log space).
# Альтернативное определение $ZPP$. Докажите, что $L \in ZPP$ тогда и только тогда, когда существует вероятностная программа $p$, которая работает за полиномиальное время, выдает 0 1 или 2, если она выдает 0 или 1, то это значение равно $x \in L$, а 2 ("не знаю") возвращается с вероятностью не больше 1/2.
# Докажите, что $ZPP = RP \cup coRP$.
# Докажите, что $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$.
# Докажите, что если для $L$ найдется программа $M$ с полиномиальным временем работы и полином $p > 0$, такие что $P(M(x) = [x \in L]) \ge \frac{1}{2} + \frac{1}{p(|x|)}$, то $L \in BPP$.
# Докажите, что если $L \in BPP$, то для любого полинома $p > 1$ найдется программа $M$ с полиномиальным временем работы, такая что $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$.
# Почему решение предыдущей задачи не удается распространить на ориентированные графы?
# Докажите, что если $NP \subset BPP$, то $NP = RP$.
# В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.
