322
правки
Изменения
→Соотношение вероятностных классов
3) <tex>\operatorname{P}(p(x) = ?) \le 1/2</tex>;
4) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>
}}
Сначала докажем, что <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex>.
<tex>\mathrm{RP} \subset \mathrm{BPP}</tex>
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in RP</tex>.Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом: q(x): u <- p(x) v <- p(x) '''return''' u '''or''' vПусть <tex>x \in L</tex>.В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.Пусть <tex>x \notin L</tex>. Тогда <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
}}
Аналогично можно показать, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
== См. также ==
