Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-zpp-notnull — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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|).
+
\mathrm{E} T_M(x) \leq p(|x|).
 
\]
 
\]
−
Докажите, что $ZPP_{NotNull}=ZPP$.
+
Докажите, что $ZPP_{NotNull}=ZPP$.
 
</latex>
 
</latex>
  
 +
[[Категория:На проверку]]
  
−
[[Category:Нерешенные задачи]]
+
===Стенина Мария, группа 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

Источник — «https://discopal.ispras.ru/index.php?title=Вероятностные_вычисления._Классы_RP,_coRP,_ZPP,_BPP/Задачи/ex-zpp-notnull&oldid=3172»