|
|
Строка 7: |
Строка 7: |
| </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>
| + | |