Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-zpp-notnull — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
<latex>Класс сложности $ZPP_{NotNull}$ состоит из всех языков $L$, для которых существует ВМТ M, | <latex>Класс сложности $ZPP_{NotNull}$ состоит из всех языков $L$, для которых существует ВМТ M, | ||
всегда возвращающая правильные ответы (т.\,е. никаких «не знаю»), причем $\exists$ полином $p(n)$, что для времени работы $T_M(x)$ машины M выполняется: | всегда возвращающая правильные ответы (т.\,е. никаких «не знаю»), причем $\exists$ полином $p(n)$, что для времени работы $T_M(x)$ машины M выполняется: | ||
− | \[ | + | \[ |
− | + | \mathrm{E} T_M(x) \leq p(|x|). | |
\] | \] | ||
− | Докажите, что $ZPP_{NotNull}=ZPP$. | + | Докажите, что $ZPP_{NotNull}=ZPP$. |
</latex> | </latex> | ||
+ | [[Категория:На проверку]] | ||
− | [[ | + | ===Стенина Мария, группа 974=== |
− | + | ||
+ | <latex> | ||
+ | Разделим доказательство на две части. | ||
+ | |||
+ | 1) $ZPP_{NotNull} \subseteq ZPP. | ||
+ | |||
+ | Пусть язык $L \in ZPP_{NotNull}$. Тогда существует ВТМ $M_2$, распознающая этот язык и работающая время, математическое ожидание которого $\mathbb{E}T_{M_2}(x) \leq p_2(|x|)$. Построим ВТМ $M_1$ следующим образом. | ||
+ | $$ | ||
+ | M_1(x) = \left\{ | ||
+ | \begin{array}{ll} | ||
+ | M_2(x), & \hbox{$T_{M_2}(x) \leq p_2(|x|)$;} \\ | ||
+ | ?, & \hbox{иначе.} | ||
+ | \end{array} | ||
+ | \right. | ||
+ | $$ | ||
+ | |||
+ | Покажем, что все свойства ZPP выполняются для $M_1$. Пусть $x \in L$. Тогда по определению $M_1$ | ||
+ | $$ | ||
+ | \mathbb{P}[M_1(x)=1] + \mathbb{P}[M_1(x)=?] = 1. | ||
+ | $$ | ||
+ | |||
+ | Вероятность получить ответ 1 $\mathbb{P}[M_1(x)=1] > \frac{1}{2}$, так как $\mathbb{E}T_{M_2}(x) \leq p_2(|x|)$, и ждем по определению ответа от $M_2$ ровно $p_2(|x|)$. | ||
+ | |||
+ | Для случая $x \not \in L$ все аналогично. | ||
+ | |||
+ | 2) $ZPP \subseteq ZPP_{NotNull}$. | ||
+ | |||
+ | Пусть язык $L \in ZPP$. Тогда существует ВТМ $M_1$, распознающая этот язык и работающая время $T_{M_1} \leq p_1(|x|)$. Построим ВТМ $M_2$ следующим образом. Для слова $x$ будем запускать $M_1$ до тех пор, пока она не даст ответ 0 или 1. | ||
+ | |||
+ | Тогда для случая $x \in L$ имеем $\mathbb{P}[M_2(x)=1]$, так как для такого слова $M_1$ может отвечать 1 или ?, а запускали ее до тех пор, пока она не дала ответ 1. Ожидаемое время работы $M_2$ при этом | ||
+ | $$ | ||
+ | \mathbb{E}T_{M_2}(x) \leq 2 T_{M_1}(x) \leq 2 p_1(|x|), | ||
+ | $$ | ||
+ | так как вероятность получить от $M_1$ ответ 1 на каждом запуске больше $\frac{1}{2}$. | ||
+ | |||
+ | Для случая $x \not \in L$ все аналогично. | ||
+ | |||
+ | Из частей 1 и 2 следует $ZPP = ZPP_{NotNull}$, что и требовалось доказать. | ||
+ | </latex> |
Версия 10:56, 31 октября 2014
Стенина Мария, группа 974