Изменения
→Соотношение вероятностных классов: program naming fixup
Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:
q(x)
'''if''' p<tex>p_2</tex>(x) = 0
'''return''' 0
'''if''' q<tex>p_1</tex>(x) = 1
'''return''' 1
'''return''' ?
Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(pp_2(x) = 1, qp_1(x) = 0) \le 1/2</tex>.
}}
