|
|
| (не показано 14 промежуточных версий этого же участника) |
| Строка 7: |
Строка 7: |
| | </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>
| + | |