Изменения
Нет описания правки
# Докажите, что если $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$ за полиномиальное время.
# Вероятностные сведения. Будем говорить, что $B$ вероятностно сводится к $C$ и писать $B \le_r C$, если найдется такая вероятностная программа $p$, работающая за полином, что $P([x \in B] = [p(x) \in C]) \ge 2/3$. Докажите, что если $C \in BPP$, $B \le_r C$, то $B \in BPP$.
# Докажите, что $\le_r$ не является транзитивным отношением.
# Класс $BP\cdot NP$ определяется как множество $\{A | A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.
# Докажите, что $BPP \subset BP\cdot NP$.
# Определим язык $UNIQUE-SAT$ как множество удовлетворимых булевых формул, которые имеют единственное удовлетворяющее назначение. Докажите, что $UNIQUE-SAT \in BP\cdot NP$.
# Докажите, что если $\overline{3SAT} \subset BP\cdot NP$, то $PH = \Sigma_3$.
