207
правок
Изменения
Нет описания правки
# Выведите из предыдущего задания, что $NL \subset NC$.
# Докажите, что $NC^1 \subset L$ ($L$ здесь log space).
# Докажите, что $BPP \subset PS$.
# Обозначим как $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 n)$ дополнительной памяти, такая что если $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$ не поменяется.
# При симуляции $random(n)$ с помощью бросков честной монеты (или абстракции вероятностной ленты) математическое ожидание времени работы $random(n)$ равно $O(\log n)$, но нет ограничения сверху на число бросков. Кажется, что это может испортить определение классов $RP$ или $BPP$, потому что в них время работы программы должно быть ограничено сверху. Докажите, что это не так и можно разрешить конструкции $random(n)$ в вероятностных программах из определения $RP$ или $BPP$, даже если на самом деле в модели вычислений есть доступ к источнику случайности только с распределением честной монеты.
# Нечестные монеты с нерациональным $p$ могут привести к парадоксам. Докажите, что существует такое $p$, такой неразрешимый язык $L$ и такая программа $A$, что если у программы $A$ есть доступ к источнику случайности с распределением нечестной монеты с вероятностью выпадения $1$ равной $p$, то она может распознать язык $L$ за полиномиальное время.
